Balon Toplama
“Şarlar səmərəli şəkildə tutulmalıdır”, oyun dizayneri deyir. O, iki ölçülü qrafikaya malik köhnə dəbli bir oyun dizayn edir. Oyunda şarlar bir-bir yerə düşür və oyunçu yer üzərində bir robot vasitəsini idarə edərək şarları tutur. Oyunçu vasitəni sola və ya sağa hərəkət etdirə və ya sadəcə yerində saxlaya bilər. Şarlardan biri yerə çatdıqda, vasitə və şar eyni mövqedə olmalıdır, əks halda şar partlayacaq və oyun sona çatacaq.
Şəkil 1: Robot vasitəsi və düşən şarlar
Oyunun məqsədi bütün şarları oyun sahəsinin sol ucundakı evə toplamaqdır. Vasitə eyni anda ən çox üç şar daşıya bilər, lakin onun sürəti daşıdığı şarların sayına görə dəyişir. Vasitə k şar daşıdıqda (k = 0, 1, 2, 3), bir vahid məsafəni hərəkət etmək üçün k+1 vaxt vahidi tələb edir. Vasitənin ümumi hərəkət məsafəsi qısa olduqda oyunçu daha yüksək xal qazanacaq.
Sizin vəzifəniz oyun dizaynerinə şar dəstindən ibarət oyun məlumatlarını yoxlamaqda kömək etməkdir. Hər bir şarın enmə mövqeyi (evdən olan məsafə kimi) və enmə vaxtı verildikdə, oyunçunun bütün şarları tuta biləcəyini mühakimə etməli və bütün şarları tutmaq və toplamaq üçün lazım olan minimum hərəkət məsafəsini cavablandırmalısınız. Vasitə evdən başlayır. Oyunçu bütün şarları tuta bilməzsə, tuta bilmədiyi ilk şarı müəyyən etməlisiniz.
Giriş verilənləri
Giriş məlumat dəstlərinin ardıcıllığıdır. Hər bir məlumat dəsti aşağıdakı kimi formatlanır.
n p_1 t_1 ... p_n t_n
Birinci sətir şarların sayını təmsil edən n tam ədədini ehtiva edir (0 < n ≤ 40). Növbəti n sətirin hər biri boşluqla ayrılmış iki tam ədəd p_i və t_i (1 ≤ i ≤ n) ehtiva edir. p_i və t_i i-ci şarın yerə çatdığı mövqeyi və vaxtı təmsil edir (0 < p_i ≤ 100, 0 < t_i ≤ 50000). t_i < t_j üçün i < j olduğunu qəbul edə bilərsiniz. Evin mövqeyi 0-dır və oyun 0 vaxtından başlayır.
Vasitənin, evin və şarların ölçüləri kifayət qədər kiçikdir və nəzərə alınmamalıdır. Vasitə şarları tutmaq və ya evə toplamaq üçün 0 vaxt tələb edir. Vasitə bu əməliyyatlardan dərhal sonra hərəkət etməyə başlaya bilər.
Girişin sonu sıfır olan bir sətirlə göstərilir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün bir sətirdə bir söz və bir tam ədəd çıxış edin, aralarında boşluq qoyun. Çıxışda əlavə simvollar olmamalıdır.
Oyunçu bütün şarları tuta bilirsə, "OK" və bütün şarları tutmaq və toplamaq üçün vasitənin minimum hərəkət məsafəsini təmsil edən bir tam ədəd çıxış edin.
Oyunçu bütün şarları tuta bilməzsə, "NG" və məlumat dəstində oyunçunun tuta bilmədiyi ilk şarın k-cı olduğunu göstərən bir tam ədəd çıxış edin.