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

注意

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

お詫び

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

問題文

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

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

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

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

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

制約

• $1 ≤ N ≤ 100000$
• $min($ 文字列 $S_i$ の長さ $) ≤ P ≤ 10^9$
• $1 ≤$( 文字列 $S_i$ の長さ )$≤ 20$
• $-10^9 ≤ H_i ≤ 10^9$

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

入力

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

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 = 2$ とするのが最適です。

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

$x = 11 , y = 17$ とするのが最適です。

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

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