Problem Statement

Ooka, who lives in the Great Okayama Empire, owns a knapsack, but he has forgotten what its capacity was.

However, there happened to be $N$ items at hand, so, in the manner of the 0-1 knapsack problem, Ooka computed the maximum value of the items in the knapsack.

Given the information on the items and the maximum value, find the minimum and maximum possible values of the capacity of Ooka's knapsack.

Strangely enough, the capacity of Ooka's knapsack is guaranteed to be an integer and at least 1.

If the maximum capacity cannot be determined, print "inf" instead of the maximum.

Input

$N$
$v_1$ $w_1$
:
$v_N$ $w_N$
$V$

The first line contains the number of items $N$.

The $N$ lines from line 2 to line $N + 1$ contain the information on the items.

Among these, the $i (1 \leq i \leq N)$-th line contains the value $v_i$ and the volume $w_i$ of the $i$-th item, separated by a space.

Line $N + 2$ contains the maximum value $V$ of the items in the knapsack.

All inputs are integers and satisfy the following constraints.

• $1 \leq N \leq 100$
• $1 \leq v_i, w_i \leq 1000$
• $0 \leq V \leq 100000$
• There exists at least one knapsack capacity $W$ with $1 \leq W \leq 100000$ for which the maximum value of the items in the knapsack is $V$

Output

$min$
$max$

On the first line, print the minimum possible value of the knapsack's capacity.

On the second line, print the maximum possible value of the knapsack's capacity, or "inf" if the maximum cannot be determined.

Print a newline at the end.

Sample

3
5 3
9 8
3 2
8

5
7

4
33 4
114 514
123 456
3 14
0

1
3

2
33 4
114 514
147

518
inf