Balloon Collection

Sanggeun is making a balloon-catching game at TGN. It is a two-dimensional game meant to captivate people's childlike wonder. In the game, balloons fall to the ground one at a time. The player drives a robot car to catch the balloons as they fall. The player can move the robot left or right, or keep it still in place. When a balloon touches the ground, the car must be exactly at that position; if the car is not there, the balloon explodes and the game ends.

The goal of the game is to store every balloon at the house on the left. The robot can carry up to $3$ balloons at a time. The robot's movement speed depends on the number of balloons it is carrying: if it is carrying $k$ balloons ($k = 0, 1, 2, 3$), moving one cell takes $(k+1)$ seconds. The less distance the robot moves, the higher the score the player earns.

Sanggeun wants to compute the highest score a player can achieve. Given the position and the time at which each balloon falls, write a program that finds the minimum number of moves the robot needs to catch every balloon and store it at the house. The robot car starts at the house. If it is impossible to catch every balloon, write a program that finds which balloon is the first one that cannot be caught.

The input consists of several test cases.

The first line of each test case contains the number of balloons $n$ ($0 < n \le 40$). Each of the next $n$ lines contains the position $p_i$ of a balloon and the time $t_i$ at which the balloon touches the ground, separated by a space ($0 < p_i \le 100$, $0 < t_i \le 50000$). For all $i < j$, $t_i < t_j$. Also, the position of the house is $0$, and the game starts at time $0$.

The sizes of the robot car, the house, and the balloons are so small that they can be ignored. The time it takes the robot to catch a balloon and the time it takes to store a balloon at the house are both $0$. Also, the car starts moving immediately after it receives a command.

The last line of the input contains a single $0$.

For each test case, print one of the following two lines.

If the player can catch every balloon, print OK and then the minimum number of moves the robot needs to catch and store all balloons. If the player cannot catch every balloon, print NG and then the number of the first balloon that cannot be caught.