풍선 수집

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

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

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

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 풍선의 개수 n이 주어진다. (0 < n ≤ 40) 다음 n개 줄에는 풍선의 위치 pi와 풍선이 땅에 닿는 시간 ti가 공백으로 구분되어 주어진다. (0 < pi ≤ 100, 0 < ti ≤ 50000) 모든 i < j에 대해서 ti < tj이다. 또, 집의 위치는 0이고, 게임은 시간이 0일 때 시작한다.

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

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

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

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