AC報酬: $15$ ラテコイン

追記

• 14:40 テストケースに不備があったので修正しました。申し訳ありませんでした。

Story

💦

matcharate君はmichirateさんが運営しているスライム研究所に行きました。
この研究所では日々、近年まれにみる謎の生物スライムの生態調査が行われています。この研究の補助員の募集をやっていたので、matcharate君はそれに参加しようと思いました。しかも報酬が他の募集よりも高い！！

ある日、michirateさんが大きいスライムを撫でながらこう言いました。

「この子、ぷるぷるさが足りなくて。どうにかして調査できるくらいのスライムのぷるぷるさにしてくれない？」

うーん...と悩んでいると、matcharate君は

「じゃあ、他の小さなスライムを合成してみるのはどうでしょうか！？！？」

と提案しました。これにはmichirateさんも脱帽です。すばらしいアイデアです。

ということで、たくさんの小さなスライムを連れてきました。合成するとなると胸がきゅっとしますが...そこらへんは目を瞑りましょう。
さらに、せっかくスライムを合成するなら大きいスライムの価値も同時に高めようと思いました。

言い忘れましたが、この小さいスライムたちは無限に沸きますが、その分能力が段々と上昇していきます。

問題

テーブルの上に $N$ 種類の子スライムがいます。
$i\ (1\le i\le N)$ 種類目の子スライムは、ぷるぷる度が $A_i$ 、価値が $B_i$ のスライムが $10^{100}$ 匹ずついます。
またすべての子スライムに対し、時間が $1$ 分経つ毎にぷるぷる度と価値が $1$ ずつ上昇します。入力で与えられたものは $0$ 分後の時です。

$1$ つの合成台にぷるぷる度 $0$ 、価値 $0$ の親スライムが乗っています。
matcharate君は $t=0,1,2,...,T$ において次の合成操作を繰り返し行います。

合成操作

• ちょうど $t$ 分が経過した後、matcharate君はすべての $i$ に対し種類 $i$ の子スライムの中から $0$ 匹以上何匹か選び(選んだ子スライムの個数を $v_1,v_2,...,v_n$ とします)、親スライムに合成する操作を行う。
  操作後、親スライムのぷるぷる度が $u+(A_1\times v_1+A_2\times v_2+\dots+A_N\times v_N)$ 、価値が $z+(B_1\times v_1+B_2\times v_2+\dots+B_N\times v_N)$ に変化する。

この合成操作を終えた後、親スライムのぷるぷる度が $K$ 以下になるように操作を行いたいと思っています。

-Mission-
適切に操作を行うことで、ちょうど $T+0.5$ 分が経つ時点で考えられる親スライムの価値の最大値はいくらになるか。報告せよ。

入力

入力は以下の形式で与えられる。

制約

• $1\le N\le 100$
• $1\le K\le 10^3$
• $0\le T\le 100$
• $1\le A_i\le 100$
• $1\le B_i\le 10^5$
• 入力はすべて整数

出力

答えを出力せよ。ただしどのように操作しても親スライムのぷるぷる度が $K$ 以下にならないなら -1 を出力せよ。

入出力例

3 5 1
2 3
1 1
3 2

7

次のように子スライムのステータスが変化します。なお子スライム $i$ のぷるぷる度 $P_i$ 、価値 $V_i$ とした数列 $P,V$ とします。

• $t=0$ 分後の時点: $P=(2,1,3),V=(3,1,2)$
• $t=1$ 分後の時点: $P=(3,2,4),V=(4,2,3)$

例えば次のように子スライムを選ぶとします。

• $0$ 分後: 子スライム $1$ を $2$ 匹、子スライム $2$ を $1$ 匹
• $1$ 分後の子スライムは一匹も選ばない

これらを親スライムに合成することで、ぷるぷる度 $2\times 2=4$ 、価値 $3\times 2+1=7$ を達成できます。これ以上価値を上げる選び方は存在しません。

3 4 5
4 2
5 1
3 3

4

例えば $0$ 分後の子スライム $3$ 、$3$ 分後の子スライム $3$ を $1$ 匹ずつ選ぶことで価値 $4$ を達成できます。

1 1000 100
1 2

2000

$0$ 分後の子スライム $1$ を $1000$ 匹選ぶことが最適です。