“气球应该被高效地收集，”游戏设计师说道。他正在设计一款采用二维画面的复古游戏。在游戏中，气球接二连三地落到地面上，玩家在地面上操控一辆机器人小车来收集这些气球。玩家可以控制小车向左、向右移动，或者直接停在原地。当其中一个气球到达地面时，小车和气球必须处于同一位置，否则气球会破裂，游戏结束。

图 B.1：机器人小车和下落的气球

游戏的目标是将所有气球收集并存放到游戏区域最左端的房子里。小车一次最多只能携带三个气球，但其移动速度会根据所携带的气球数量而改变。当小车携带 $k$ 个气球（$k = 0, 1, 2, 3$）时，移动一个单位的距离需要花费 $k+1$ 个单位的时间。小车的总移动距离越短，玩家获得的分数就越高。

你的任务是帮助游戏设计师检查由一组气球组成的游戏数据。给定每个气球的着陆位置（即到房子的距离）和着陆时间，你必须判断玩家是否能够收集到所有的气球，并回答收集并存放所有气球所需的最小移动距离。小车从房子出发。如果玩家无法收集到所有的气球，你必须确定玩家无法收集到的第一个气球。

输入格式

输入由多个数据集组成。每个数据集的格式如下：

$$ \begin{aligned} &n \\ &p_1 \quad t_1 \\ &\vdots \\ &p_n \quad t_n \end{aligned} $$

第一行包含一个整数 $n$，表示气球的数量（$0 < n \le 40$）。接下来的 $n$ 行中，每行包含两个由空格隔开的整数 $p_i$ 和 $t_i$（$1 \le i \le n$）。$p_i$ 和 $t_i$ 分别表示第 $i$ 个气球到达地面的位置和时间（$0 < p_i \le 100$，$0 < t_i \le 50000$）。你可以假设对于 $i < j$，有 $t_i < t_j$。房子的位置为 $0$，游戏从时间 $0$ 开始。

小车、房子和气球的大小足够小，可以忽略不计。小车收集气球或将气球存入房子不需要花费时间。小车在完成这些操作后可以立即开始移动。

输入结束由包含一个零（0）的行表示。

输出格式

对于每个数据集，在一行中输出一个单词和一个整数，中间用空格隔开。输出中不应出现多余的字符。

• 如果玩家可以收集到所有的气球，输出 “OK” 和一个整数，表示小车收集并存放所有气球所需的最小移动距离。
• 如果玩家无法收集到所有的气球，输出 “NG” 和一个整数 $k$，表示数据集中第 $k$ 个气球是玩家无法收集到的第一个气球。

样例

输入样例 1

2
10 100
100 270
2
10 100
100 280
3
100 150
10 360
40 450
3
100 150
10 360
40 440
2
100 10
50 200
2
100 100
50 110
1
15 10
4
1 10
2 20
3 100
90 200
0

输出样例 1

OK 220
OK 200
OK 260
OK 280
NG 1
NG 2
NG 1
OK 188