Збирання повітряних кульок
“Кулі повинні бути захоплені ефективно”, каже дизайнер гри. Він розробляє старомодну гру з двовимірною графікою. У цій грі кулі падають на землю одна за одною, і гравець керує роботизованим транспортним засобом, щоб їх захопити. Гравець може переміщувати транспортний засіб вліво або вправо, або залишати його на місці. Коли куля досягає землі, транспортний засіб повинен бути в тій самій позиції, інакше куля лусне і гра закінчиться.
Рисунок 1: Роботизований транспортний засіб і падаючі кулі
Мета гри — зберегти всі кулі в будинку, розташованому на лівому кінці ігрового поля. Транспортний засіб може перевозити не більше трьох куль одночасно, але його швидкість залежить від кількості перевезених куль. Коли транспортний засіб перевозить k куль (k = 0, 1, 2, 3), йому потрібно k+1 одиниць часу, щоб переміститися на одну одиницю відстані. Гравець отримає вищий бал, якщо загальна відстань переміщення транспортного засобу буде меншою.
Ваше завдання — допомогти дизайнеру гри перевірити дані гри, що складаються з набору куль. Враховуючи позицію приземлення (як відстань від будинку) і час приземлення кожної кулі, ви повинні визначити, чи може гравець захопити всі кулі, і знайти мінімальну відстань переміщення, необхідну для захоплення і зберігання всіх куль. Транспортний засіб починає рух з будинку. Якщо гравець не може захопити всі кулі, ви повинні визначити першу кулю, яку гравець не може захопити.
Вхідні дані
Вхідні дані складаються з послідовності наборів даних. Кожен набір даних має наступний формат.
n p_1 t_1 ... p_n t_n
Перший рядок містить ціле число n, яке представляє кількість куль (0 < n ≤ 40). Кожен з наступних n рядків містить два цілі числа p_i і t_i (1 ≤ i ≤ n), розділені пробілом. p_i і t_i представляють позицію і час, коли i-та куля досягає землі (0 < p_i ≤ 100, 0 < t_i ≤ 50000). Ви можете припустити, що t_i < t_j для i < j. Позиція будинку - 0, і гра починається з часу 0.
Розміри транспортного засобу, будинку і куль достатньо малі, і їх слід ігнорувати. Транспортний засіб потребує 0 часу для захоплення куль або зберігання їх у будинку. Транспортний засіб може почати рух відразу після цих операцій.
Кінець введення позначається рядком, що містить нуль.
Вихідні дані
Для кожного набору даних виведіть одне слово і одне ціле число в рядку, розділені пробілом. Не повинно бути зайвих символів у виведенні.
Якщо гравець може захопити всі кулі, виведіть "OK" і ціле число, яке представляє мінімальну відстань переміщення транспортного засобу для захоплення і зберігання всіх куль.
Якщо неможливо для гравця захопити всі кулі, виведіть "NG" і ціле число k, таке, що k-та куля в наборі даних є першою кулею, яку гравець не може захопити.