Збирання повітряних кульок#3460

Збирання повітряних кульок

1 секунда

32 мегабайти

Складна

"Кулі повинні бути захоплені ефективно", каже дизайнер гри. Він розробляє старомодну гру з двовимірною графікою. У цій грі кулі падають на землю одна за одною, і гравець керує роботизованим транспортним засобом, щоб їх захопити. Гравець може переміщувати транспортний засіб вліво або вправо, або залишати його на місці. Коли куля досягає землі, транспортний засіб повинен бути в тій самій позиції, інакше куля лусне і гра закінчиться.

Рисунок 1: Роботизований транспортний засіб і падаючі кулі

Мета гри — зберегти всі кулі в будинку, розташованому на лівому кінці ігрового поля. Транспортний засіб може перевозити не більше трьох куль одночасно, але його швидкість залежить від кількості куль, що перевозяться. Коли транспортний засіб перевозить $k$ куль ( $k = 0, 1, 2, 3$ k = 0, 1, 2, 3), йому потрібно $k + 1$ k+1 одиниць часу, щоб переміститися на одну одиницю відстані. Гравець отримає вищий бал, якщо загальна відстань переміщення транспортного засобу буде меншою.

Ваше завдання — допомогти дизайнеру гри перевірити дані гри, що складаються з набору куль. Враховуючи позицію приземлення (як відстань від будинку) і час приземлення кожної кулі, ви повинні визначити, чи може гравець захопити всі кулі, і знайти мінімальну відстань переміщення, необхідну для захоплення і зберігання всіх куль. Транспортний засіб починає рух з будинку. Якщо гравець не може захопити всі кулі, ви повинні визначити першу кулю, яку гравець не може захопити.

Вхідні дані

Вхідні дані складаються з послідовності наборів даних. Кожен набір даних має наступний формат.

$n$ $p_{1}$ p_1 $t_{1}$ t_1 ... $p_{n}$ p_n $t_{n}$ t_n

Перший рядок містить ціле число $n$ , яке представляє кількість куль ( $0 < n \leq 40$ 0 < n \leq 40). Кожен з наступних $n$ рядків містить два цілі числа $p_{i}$ p_i і $t_{i}$ t_i ( $1 \leq i \leq n$ 1 \leq i \leq n), розділені пробілом. $p_{i}$ p_i і $t_{i}$ t_i представляють позицію і час, коли $i$ -та куля досягає землі ( $0 < p_{i} \leq 100$ 0 < p_i \leq 100, $0 < t_{i} \leq 50000$ 0 < t_i \leq 50000). Ви можете припустити, що $t_{i} < t_{j}$ t_i < t_j для $i < j$ i < j. Позиція будинку - $0$ , і гра починається з часу $0$ .

Розміри транспортного засобу, будинку і куль достатньо малі, і їх слід ігнорувати. Транспортний засіб потребує $0$ часу для захоплення куль або зберігання їх у будинку. Транспортний засіб може почати рух відразу після цих операцій.

Кінець введення позначається рядком, що містить нуль.

Вихідні дані

Для кожного набору даних виведіть одне слово і одне ціле число в рядку, розділені пробілом. Не повинно бути зайвих символів у виведенні.

Якщо гравець може захопити всі кулі, виведіть "OK" і ціле число, яке представляє мінімальну відстань переміщення транспортного засобу для захоплення і зберігання всіх куль.
Якщо неможливо для гравця захопити всі кулі, виведіть "NG" і ціле число $k$ , таке, що $k$ -та куля в наборі даних є першою кулею, яку гравець не може захопити.

Приклади

Приклад 1