Time-6 - Make you Stronger

2 secs 1024 MB
matcharate12's icon matcharate12

AC報酬: 1515 ラテコイン

追記

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

Story

💦

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

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

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

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

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

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

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

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

問題

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

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

合成操作

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

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

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

入力

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

NNKKTT
A1A_1B1B_1
A2A_2B2B_2
\vdots
ANA_NBNB_N

制約

  • 1N1001\le N\le 100
  • 1K1031\le K\le 10^3
  • 0T1000\le T\le 100
  • 1Ai1001\le A_i\le 100
  • 1Bi1051\le B_i\le 10^5
  • 入力はすべて整数

出力

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

入出力例

入力例1
3 5 1
2 3
1 1
3 2
出力例1
7

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

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

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

  • 00 分後: 子スライム 1122 匹、子スライム 2211
  • 11 分後の子スライムは一匹も選ばない

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

入力例2
3 4 5
4 2
5 1
3 3
出力例2
4

例えば 00 分後の子スライム 3333 分後の子スライム 3311 匹ずつ選ぶことで価値 44 を達成できます。

入力例3
1 1000 100
1 2
出力例3
2000

00 分後の子スライム 1110001000 匹選ぶことが最適です。

Submit


Go (1.21)