Сбор воздушных шаров
«Шары должны быть захвачены эффективно», — утверждает разработчик игры. Он создает ретро-игру с двухмерной графикой. В этой игре шары падают на землю один за другим, и игрок управляет роботизированным транспортным средством, чтобы ловить их. Игрок может перемещать транспортное средство влево или вправо или оставаться на месте. Если шар достигает земли, транспортное средство должно находиться в той же позиции, иначе шар лопнет, и игра закончится.
Рисунок 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-й шар в наборе данных — это первый шар, который игрок не может захватить.