I heard there is a Hidden Command to become Happy. (Easy)

2 secs 1024 MB
OxOmiso

問題文


ゆかりさんは、人生を生きています。
これからの人生の中で、 個のイベントが発生します。
各イベントは文字列 と整数値 で表され、各イベント について、それを行うことで得られる「幸福度」と「疲労度」が以下の様に決まっています。

  • 各イベント の「幸福度」は である。
  • 各イベント の「疲労度」は文字列 の文字数である。

例えば、 = LEFT = の場合、イベント を行うことで得られる疲労度は 、幸福度は です。

ゆかりさんには、耐久度が決まっていて、自然数 で与えられます。
行うイベントの疲労度の合計が 以下 でないと、ゆかりさんは耐えられません。
そこで、ゆかりさんは、 である整数 を選んで、イベント のみ行うことにしました。

のイベントを終えた後の幸福度を「人生の幸福度」とするとき、「人生の幸福度」の最大値を求めてください。

制約


  • 文字列 の長さ
  • ( 文字列 の長さ )

入力


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

N P
S_1 H_1
S_2 H_2
:
:
S_N H_N

出力


得られる「人生の幸福度」の最大値を一行に出力してください。

入力例 1


3 5
UP 3
RIGHT 14
LEFT 1

出力例 1


14

とするのが最適です。

入力例 2


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

出力例 2


273

入力例 3


5 100
job 0
betrayal 0
assignment 0
illness 0
burden 0

出力例 3


0

可哀想なことに、これから起こる全てのイベントの幸福度が です。しかし、 を選んで必ず1つ以上はイベントを行わないといけません。

入力例 4


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

出力例 4


1000000000000000100

とするのが最適です。
幸福度が のイベントを避けて RESET だけ行うのは、最適ではないことに注意してください。
また、ゆかりさんにとって、RESET が最も幸福なことのようです。

Submit


Go (1.14)