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

2 secs 1024 MB
OxOmiso

注意


この問題は、 Easy 版の問題と、制約と一部問題設定が異なります。

お詫び


作問者の解法が誤っていました。現在は修正されています。大変申し訳ございません。2021/11/16 23:25

問題文


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

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

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

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

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

制約


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

Easy版の問題の制約と異なり,幸福度 が負の整数値を取り得るようになっています。ご注意ください。

入力


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

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


19 20
UP 3
DOWN 75
RIGHT -6
L 4
DOWN -187
SELECT 8
START 21
R -8
SELECT -78
LEFT -2
LEFT 375
A 6
DOWN 4
LEFT 44
UP -44
LEFT 470
X 47
A -4
L -7

出力例 2


902

とするのが最適です。

入力例 3


5 100
job -10000
betrayal -10000000
assignment -10000
illness -100
burden -100000

出力例 3


0

可哀想なことに、これから起こる全てのイベントの幸福度が負です。

入力例 4


13 1000 
sns 206603
powerharassment -18782
entranceexam -18782
sexualharassment -18782
graduationthesis -18782
findingjob -18782
ageharassment -18782
alcoholharassment -18782
overtimework -18782
responsibility -18782
marriageharassment -18782
slander -18782
RESET 999999999

出力例 4


1000000000

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

提出


Go (1.14)