풍선 수집

상근이는 TGN에서 풍선을 잡는 게임을 만들고 있다. 이 게임은 사람들의 동심을 사로잡을 이차원 게임이다. 게임에서 풍선은 하나씩 땅으로 떨어진다. 플레이어는 로봇 자동차를 조종해서 땅으로 떨어지는 풍선을 잡는다. 플레이어는 로봇을 왼쪽이나 오른쪽으로 움직이거나 그 자리에 멈춰 있게 할 수 있다. 어떤 풍선이 땅에 닿을 때 반드시 그 위치에 로봇 자동차가 있어야 한다. 만약 차량이 없다면 풍선은 폭발하고 게임은 끝난다.

게임의 목표는 모든 풍선을 왼쪽에 있는 집에 보관하는 것이다. 로봇은 풍선을 한 번에 $3$개까지 운반할 수 있다. 로봇의 이동 속도는 운반하는 풍선의 개수에 따라 달라져서, 운반하고 있는 풍선이 $k$개($k = 0, 1, 2, 3$)라면 한 칸 움직이는 데 $(k+1)$초가 걸린다. 플레이어는 로봇이 움직이는 거리가 적을수록 더 높은 점수를 얻는다.

상근이는 플레이어가 얻을 수 있는 최고 점수를 계산해 보려고 한다. 풍선이 떨어지는 위치와 시간이 주어졌을 때, 모든 풍선을 잡아서 집에 저장하기 위한 로봇의 최소 이동 횟수를 구하는 프로그램을 작성하시오. 로봇 자동차는 집에서 시작한다. 만약 모든 풍선을 잡을 수 없다면, 잡지 못하는 첫 번째 풍선이 무엇인지 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 풍선의 개수 $n$이 주어진다 ($0 < n \le 40$). 다음 $n$개 줄에는 풍선의 위치 $p_i$와 풍선이 땅에 닿는 시간 $t_i$가 공백으로 구분되어 주어진다 ($0 < p_i \le 100$, $0 < t_i \le 50000$). 모든 $i < j$에 대해서 $t_i < t_j$이다. 또, 집의 위치는 $0$이고, 게임은 시간이 $0$일 때 시작한다.

로봇 자동차, 집, 풍선의 크기는 매우 작아서 무시할 수 있다. 로봇이 풍선을 잡는 데 걸리는 시간과 집에 풍선을 보관하는 데 걸리는 시간은 $0$이다. 또, 자동차는 명령을 받은 후 즉시 움직인다.

입력의 마지막 줄에는 $0$이 하나 주어진다.

각 테스트 케이스에 대해서, 다음 두 가지 중 하나를 출력한다.

만약 플레이어가 모든 풍선을 잡을 수 있다면 OK를 출력한 뒤, 로봇이 풍선을 모두 잡고 보관하는 데 필요한 최소 이동 횟수를 출력한다. 플레이어가 모든 풍선을 잡을 수 없다면 NG를 출력한 뒤, 잡을 수 없는 첫 번째 풍선의 번호를 출력한다.