该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：pack.in 输出文件：pack.out

小明有一个背包，但他忘了这个背包的容量是多少了。

不过，刚好那里有 $N$ 个行李，于是小明参照 “0-1背包问题”，尝试计算了背包内可装入行李的最大价值。

现在已知行李的信息（重量、价值等）以及计算出的最大价值，请你求出小明背包容量可能的最小值和最大值。

需要注意的是，小明的背包容量必定是整数，且题目保证其容量不小于 $1$。

另外，若容量的最大值无法确定（即不存在上限），则输出 “inf” 来替代最大值。

补充说明：“0-1背包问题”是指从 $N$ 个物品（每个物品有重量和价值）中挑选若干个放在一个总重量限制的背包内，在物品重量之和不超过背包总重量限制的情况下要取得最大的价值和。

输入格式

第一行一个整数 $N$ 表示行李的数量。

后面 $N$ 行，每行两个整数 $v_i,w_i$ 表示一件行李的价值和重量。

最后一行一个整数 $V$ 表示计算出的背包内可装入行李的最大价值。

输出格式

第一行一个整数，表示背包的最小容量。

第二行一个整数或者 "inf"，表示背包的最大容量。

样例

样例 1

3
5 3
9 8
3 2
8

5
7

样例 2

4
33 4
114 514
123 456
3 14
0

1
3

样例 3

2
33 4
114 514
147

518
inf

数据范围

$1 \le N \le 100$

$1 \le v_i,w_i \le 1000$

$1 \le V \le 100000$

至少存在一个在 $1 \leq W \leq 100000$ 的范围内的背包容量 $W$ 能使背包内价值最大值为 $V$。