問題文

グレート岡山大国に住む大岡くんは, あるナップサックを持っていますが, 容量がどのくらいだったか忘れてしまいました.

ただ, ちょうどそこに $N$ 個の荷物があったので, 大岡くんは0-1ナップサック問題よろしくナップサック内の価値の最大値を求めてみました.

荷物の情報と価値の最大値の情報が与えられるので, 大岡くんのナップサックの容量として考えられる値の最小値と最大値を求めてください.

ただし, 不思議なことに大岡くんのナップサックの容量は必ず整数で, 1以上であることが保障されています.

また, 容量の最大値が定まらなかった場合, 最大値の代わりに "inf" と出力してください.

入力

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

1行目に, 品物の個数 $N$ が与えられます.

2行目から $N+1$行目までの $N$ 行の間, 荷物の情報が与えられます.

このうち $i(1\le i\le N)$ 行目には $i$ 番目の荷物の価値 $v_i$ と容積 $w_i$ が空白区切りで与えられます.

$N+2$ 行目にナップサック内の価値の最大値 $V$ が与えられます.

入力は全て整数で, 以下の制約を満たします.

• $1\le N\le 100$
• $1\le v_i,w_i\le 1000$
• $0\le V\le 100000$
• ナップサック内の価値の最大値が $V$ となるナップサックの容量 $W$ が, $1\le W\le 100000$ に少なくとも一つ存在する

出力

$min$
$max$

1行目にナップサックの容量として考えられる値の最小値を,

2行目にナップサックの容量として考えられる値の最大値, または最大値が定まらない場合は "inf" を出力してください.

最後に改行してください.

サンプル

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