You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

作为一名忙碌的商人，约翰知道必须高效地安排他的时间。他有 $N(1\le N\le 1000)$ 个工作要做，比如给奶牛挤奶，清洗牛棚，修理栅栏之类的。

为了高效，约翰列出了所有工作的清单。第 $i(1\le i\le N)$ 个工作需要 $T_i(1\le T_i\le 1000)$ 单位的时间来完成，而且必须在 $1\le S_i\le 10^6$ 或之前完成。现在是 $0$ 时刻。约翰做一份工作必须直到做完才能停止。

所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作，可以让所有工作按时完成。（如果始终无法完成全部任务，输出 -1）

输入格式

第一行，一个整数 $N$

接下来 $N$ 行，每行 $2$ 个有空格分隔的整数 $T_i,S_i$

输出格式

一行，一个整数，表示约翰可以开始工作的最晚时间，如果约翰无法完成所有工作，则为 -1

4 
3 5 
8 14 
5 20 
1 16 

2 

提示

【样例解释】

约翰有 $4$ 个工作要做，分别需要 $3、8、5$ 和 $1$ 个时间单位，并且必须分别在时间 $5、14、20$ 和 $16$ 之前完成。

约翰必须在时间 $2$ 开始第一个作业。然后他可以按此顺序完成第二、第四和第三项工作，以按时完成。