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

2 secs 1024 MB
OxOmiso's icon OxOmiso

問題文

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

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

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

ゆかりさんには、耐久度が決まっていて、自然数 PP で与えられます。
行うイベントの疲労度の合計が PP 以下 でないと、ゆかりさんは耐えられません。
そこで、ゆかりさんは、1xyN1≤x≤y≤N である整数 x,yx,y を選んで、イベント Sx,Sx+1,Sx+2,,Sy1,SyS_x , S_{x+1} , S_{x+2} , … , S_{y-1} , S_y のみ行うことにしました。

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

制約

  • 1N1000001 ≤ N ≤ 100000
  • min(min( 文字列 SiS_i の長さ )P109) ≤ P ≤ 10^9
  • 11 ≤ ( 文字列 SiS_i の長さ )20 ≤ 20
  • 0Hi1090 ≤ H_i ≤ 10^9

入力

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

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

x=2,y=2x = 2 , y = 2 とするのが最適です。

入力例 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

可哀想なことに、これから起こる全てのイベントの幸福度が 00 です。しかし、x,yx,y を選んで必ず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

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

提出


Go (1.21)