ゆかりさんは、人生を生きています。
これからの人生の中で、 個のイベントが発生します。
各イベントは文字列 と整数値 で表され、各イベント について、それを行うことで得られる「幸福度」と「疲労度」が以下の様に決まっています。
例えば、 = LEFT
、 = の場合、イベント を行うことで得られる疲労度は 、幸福度は です。
ゆかりさんには、耐久度が決まっていて、自然数 で与えられます。
行うイベントの疲労度の合計が 以下 でないと、ゆかりさんは耐えられません。
そこで、ゆかりさんは、 である整数 を選んで、イベント のみ行うことにしました。
のイベントを終えた後の幸福度を「人生の幸福度」とするとき、「人生の幸福度」の最大値を求めてください。
入力は以下の形式で与えられます。
N P S_1 H_1 S_2 H_2 : : S_N H_N
得られる「人生の幸福度」の最大値を一行に出力してください。
3 5 UP 3 RIGHT 14 LEFT 1
14
とするのが最適です。
20 20 UP 25 DOWN 70 RIGHT 18 L 39 DOWN 84 SELECT 49 START 40 R 16 SELECT 61 LEFT 81 LEFT 13 A 11 DOWN 12 LEFT 3 UP 1 LEFT 34 X 43 A 16 L 60 Y 93
273
5 100 job 0 betrayal 0 assignment 0 illness 0 burden 0
0
可哀想なことに、これから起こる全てのイベントの幸福度が です。しかし、 を選んで必ず1つ以上はイベントを行わないといけません。
13 1000 sns 100 powerharassment 0 entranceexam 0 sexualharassment 0 graduationthesis 0 findingjob 0 ageharassment 0 alcoholharassment 0 overtimework 0 responsibility 0 marriageharassment 0 slander 0 RESET 1000000000000000000
1000000000000000100
とするのが最適です。
幸福度が のイベントを避けて RESET
だけ行うのは、最適ではないことに注意してください。
また、ゆかりさんにとって、RESET
が最も幸福なことのようです。