记录编号	48667	评测结果	AAAAAAAA
题目名称	过河	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2012-11-06 13:09:49	内存使用	1.97 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=1011;
int N,A[MAXN],B[MAXN];
bool F[2][MAXN]={0};int MS=0;

inline void init()
{
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++)
		scanf("%d %d\n",&A[i],&B[i]);
	MS+=(*max_element(A+1,A+1+N));
	MS+=(*max_element(B+1,B+1+N));
	MS*=(N+1);
	A[0]=MS*10,A[N+1]=MS*10;
}

inline void dp()
{
	F[0][0]=1;
	for(int i=1;i<=MS;i++)
	{
		int now=i%2,pre=(i-1)%2;
		for(int j=0;j<=N+1;j++)
		{
			F[now][j]=0;
			if( ((i%(A[j]+B[j]))==0) || ((i%(A[j]+B[j]))>A[j])) continue;
			for(int k=(j-5<0?0:j-5);k<=(j+5>N+1?N+1:j+5);k++)
				if(F[pre][k]) {F[now][j]=1;break;}
		}
		//printf("%d  %d %d--> ",i,now,pre);
	//	for(int j=0;j<=N+1;j++) printf("%d ",F[now][j]);
	//	printf("\n");
		if(F[now][N+1]) {printf("%d\n",i);return;}
	}
	printf("NO\n");
}

int main()
{
	freopen("rivera.in","r",stdin);
	freopen("rivera.out","w",stdout);
	init(); dp();
	return 0;
}

/*
溜息に融け込んだ　アナクロめいた十（とお）の指と 
贅沢に混ぜ込んだ　自由に泣いた少女は言った

「虫の音よ絶えゆくなよ」　一鳴き応え窓の縁 
月の端（は）も暈（ぼ）かす憂世（うきよ）に　踊る人影

薫（かお）り　誘い　また拐（かどわ）かす 
悲し　愉（たの）し　奏（かなで）の織糸（いと）は 
彩葉（いろは）　撫（な）ぜる　夢弦（むげん）の調（しらべ） 
朽ちた恋（はな）まで　芽吹くようで

裸足で忍び込んだ　白黒絨毯（じゅうたん）　毎夜の青眼 
奇（あや）しげに洒落（しゃれ）込んだ　光の中　男は言った

「僕の音を君に託そう」　千秋（ちあき）の風に泣き濡れた 
刻む指　震わす弓は　殊更（ことさら）に烈（はげ）しく

ひらり　わらう　世の不条理と 
冬の跫（あしおと）に抱かれて 
出逢い　別れ　然（さ）れども止まぬ 
経緯（たてよこ）の愛（いと）は　永久（とわ）の夢

「君の音よ　明日はきっと」　祈り呟く窓の外 
指先に一片（ひとひら）の葉 ―――

ただ散りゆく花弁に涙も忘れてた

月に　雪に　鳴く螽斯（きりぎりす） 
どうか　君に　聞こえるならば 
春に　恋（はな）に　奏でておくれ 
垂らす　この愛（いと）に　絡ませて

出逢い　別れ　背中合わせた 
悲し　愛（かな）し　奏（かなで）の織糸（いと）は 
枯れた　恋（はな）に　羽衣着せて 
麗しき実を結ぶでしょう

君の温もりに眠らせて
*/