AOJ1306.cpp

#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };
struct state{
	int cap;
	int have;
	int move;
};
bool operator <(const state& left, const state& right){
	return left.move > right.move;
}
int main() {
	int n;
	while (cin >> n, n){
		vector<pair<int, int>> balloon(n + 1, { 0, 0 });
		REP(i, n){
			cin >> balloon[i + 1].first >> balloon[i + 1].second;//p,t
		}
		vector<vector<int>> dp(3,vector<int>(n,10000));
		bool clear = false;
		int ans;
		int ma = 1;
		priority_queue<state> P;//time,cap,having,move
		P.push({ 0, 0, 0 });
		while (!P.empty()){
			state st = P.top(); P.pop();
			if (st.cap == n){
				ans = st.move + balloon[st.cap].first;
				clear = true;
				break;
			}
			//戻ってから行く
			if (balloon[st.cap + 1].second >= balloon[st.cap].first*(st.have + 1) + balloon[st.cap + 1].first + balloon[st.cap].second)
				if (dp[0][st.cap]>st.move + balloon[st.cap + 1].first + balloon[st.cap].first){
					P.push({ st.cap + 1, 1, st.move + balloon[st.cap + 1].first + balloon[st.cap].first });
					dp[0][st.cap] = st.move + balloon[st.cap + 1].first + balloon[st.cap].first;
				}
			//そのまま直行
			if (st.have <= 2)
				if (balloon[st.cap + 1].second >= abs(balloon[st.cap + 1].first - balloon[st.cap].first)*(st.have + 1) + balloon[st.cap].second)
					if (dp[st.have ][st.cap]>st.move + abs(balloon[st.cap + 1].first - balloon[st.cap].first)){
						P.push({ st.cap + 1, st.have + 1, st.move + abs(balloon[st.cap + 1].first - balloon[st.cap].first) });
						dp[st.have ][st.cap] = st.move + abs(balloon[st.cap + 1].first - balloon[st.cap].first);
					}
			ma = max(ma, st.cap + 1);
		}
		if (clear){
			cout << "OK " << ans << endl;
		}
		else{
			cout << "NG " << ma << endl;
		}
	}
}