JOI 君の部屋にはストーブがある．JOI 君自身は寒さに強いのでひとりで部屋にいるときはストーブをつける必要はないが，来客があるときはストーブをつける必要がある．

この日，JOI 君のもとには N 人の来客がある．i 番目 (1 \leqq i \leqq N) の来客は時刻 T_i に到着し，時刻 T_i + 1 に退出する．同時に複数人の来客があることはない．

JOI 君は任意の時刻にストーブをつけたり消したりできる．ただし，ストーブをつける度にマッチを 1 本消費する．JOI 君はマッチを K 本しか持っていないので，K 回までしかストーブをつけることができない．一日のはじめにストーブは消えている．

ストーブをつけているとその分だけ燃料を消費するので，ストーブをつけたり消したりする時刻をうまく定めて，ストーブがついている時間の合計を最小化したい．

課題

JOI 君の部屋への来客の情報と，JOI 君の持っているマッチの本数が与えられたとき，ストーブがついている時間の合計の最小値を求めよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq N \leqq 100\,000．
• 1 \leqq K \leqq N．
• 1 \leqq T_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• T_i < T_{i+1} (1 \leqq i \leqq N - 1)．

小課題

小課題 1 [20 点]

以下の条件を満たす．

• N \leqq 20．
• 1 \leqq T_i \leqq 20 (1 \leqq i \leqq N)．

小課題 2 [30 点]

• N \leqq 5\,000 を満たす．

小課題 3 [50 点]

• 追加の制限はない．

入力例 1

3 2
1
3
6

出力例 1

4

この入力例では，JOI 君の部屋への来客が 3 人ある．以下のようにストーブをつけたり消したりすると，来客がある間はストーブがついており，ストーブをつける回数は 2 回であり，ストーブがついている時間の合計は (4 - 1) + (7 - 6) = 4 である．

• 1 番目の来客が到着する時刻 1 にストーブをつける．
• 2 番目の来客が退出する時刻 4 にストーブを消す．
• 3 番目の来客が到着する時刻 6 にストーブをつける．
• 3 番目の来客が退出する時刻 7 にストーブを消す．

ストーブをつけている時間の合計を 4 未満にすることはできないので，答えとして 4 を出力する．

入力例 2

3 1
1
2
6

出力例 2

6

この入力例では，JOI 君は 1 回しかストーブをつけることができないので，1 番目の来客が到着する時刻1 にストーブをつけ，3 番目の来客が退出する時刻 7 にストーブを消せばよい．

来客が退出する時刻と，その次の来客が到着する時刻が一致する場合があることに注意せよ．

入力例 3

3 3
1
3
6

出力例 3

3

この入力例では，JOI 君は来客が到着する度にストーブをつけ，来客が退出する度にストーブを消せばよい．

入力例 4

10 5
1
2
5
6
8
11
13
15
16
20

出力例 4

12

JOI 国で美術展が行われることになった．美術展では，国中から集まった様々な美術品が展示される予定である．

展示される美術品の候補として，N 点の美術品が集まった．これらの美術品には 1, 2, \ldots, N の番号が付けられている．それぞれの美術品には大きさと価値と呼ばれる値が定まっている．美術品 i (1 \leqq i \leqq N) の大きさは A_i，価値は B_i である．

美術展では，これらの美術品のうちから 1 点以上を選んで展示する．美術展の会場は十分に広く，N 点の美術品すべてを展示することも可能である．しかし，JOI 国の人々の美的感覚のため，美術品の間で大きさの差があまり大きくならないように展示する美術品を選びたい．一方，できるだけ価値の大きい美術品を多く展示したい．そのため，次の条件を満たすように展示する美術品を選ぶことにした：

• 選んだ美術品の中で，大きさが最大のものの大きさを A_{\mathrm{max}}，最小のものの大きさを A_{\mathrm{min}} とする．また，選んだ美術品の価値の総和を S とする．
• このとき，S - (A_{\mathrm{max}} - A_{\mathrm{min}}) を最大化する．

課題

展示される美術品の候補の個数と，それぞれの美術品の大きさと価値が与えられたとき，S - (A_{\mathrm{max}} - A_{\mathrm{min}}) の最大値を求めよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 500\,000．
• 1 \leqq A_i \leqq 1\,000\,000\,000\,000\,000 = 10^{15} (1 \leqq i \leqq N)．
• 1 \leqq B_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．

小課題

小課題 1 [10 点]

• N \leqq 16 を満たす．

小課題 2 [20 点]

• N \leqq 300 を満たす．

小課題 3 [20 点]

• N \leqq 5\,000 を満たす．

小課題 4 [50 点]

• 追加の制限はない．

入力例 1

3
2 3
11 2
4 5

出力例 1

6

この入力例では，展示される美術品の候補が 3 点ある．それぞれの美術品の大きさ，価値は次の通りである．

• 美術品 1 の大きさは 2，価値は 3 である．
• 美術品 2 の大きさは 11，価値は 2 である．
• 美術品 3 の大きさは 4，価値は 5 である．

この場合，美術品 1 と美術品 3 を展示するために選ぶと，次のようにして S - (A_{\mathrm{max}} - A_{\mathrm{min}}) = 6 となる．

• 選んだ中で大きさが最大の美術品は，美術品 3 である．よって，A_{max} = 4 である．
• 選んだ中で大きさが最小の美術品は，美術品 1 である．よって，A_{min} = 2 である．
• 選んだ美術品の価値の総和は 3 + 5 = 8 であるから，S = 8 である．

S - (A_{max} - A_{min}) を 7 以上にすることは不可能なので，6 を出力する．

入力例 2

6
4 1
1 5
10 3
9 1
4 2
5 3

出力例 2

7

入力例 3

15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562

出力例 3

4232545716

あなたは団子を作る職人である．今，あなたは団子に串を刺そうとしているところである．

団子は，縦 N 行，横 M 列に仕切られたマスの中に配置されている．各マスには団子が 1 個ずつ入っている．それぞれの団子には，赤 (R)，緑 (G)，白 (W) のいずれかの色が付いている．あなたは，左から右の方向，または，上から下の方向に連続する 3 マスから団子を取り出し，この順に 1 本の串にちょうど 3 個刺すことができる．

今あなたは，赤，緑，白の団子が 1 個ずつこの順に刺さった串を可能な限り多く作りたい．串に刺す順番は，マスから取り出した順番と同じでなければならない．また，同じ団子に 2 本以上の串を刺すことはできない．

あなたは，団子が刺さった串を最大何本作ることができるだろうか．

課題

マスの中に配置された団子の色の情報が与えられたとき，赤，緑，白の団子が 1 個ずつこの順に刺さった串が最大何本作れるかを求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq N \leqq 3\,000．
• 1 \leqq M \leqq 3\,000．

小課題

小課題 1 [13 点]

以下の条件を満たす．

• N \leqq 4．
• M \leqq 4．

小課題 2 [20 点]

以下の条件を満たす．

• N \leqq 10．
• M \leqq 10．

小課題 3 [67 点]

追加の制限はない．

入力例 1

3 4
RGWR
GRGG
RGWW

出力例 1

3

次のように串に刺すことで，団子が刺さった串を 3 本作ることができる．

• 上から 1 行目，左から 1 列目の団子から右方向に 3 個の団子を取り出し，この順に串に刺す．
• 上から 1 行目，左から 4 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
• 上から 3 行目，左から 1 列目の団子から右方向に 3 個の団子を取り出し，この順に串に刺す．

4 本以上の串を作ることはできないので，3 を出力する．

入力例 2

4 4
RGWR
GRRG
WGGW
WWWR

出力例 2

4

次のように串に刺すことで，団子が刺さった串を 4 本作ることができる．

• 上から 1 行目，左から 1 列目の団子から右方向に 3 個の団子を取り出し，この順に串に刺す．
• 上から 1 行目，左から 4 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
• 上から 2 行目，左から 2 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．
• 上から 2 行目，左から 3 列目の団子から下方向に 3 個の団子を取り出し，この順に串に刺す．

5 本以上の串を作ることはできないので，4 を出力する．

入力例 3

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW

出力例 3

6

JOI 君が住む都市には N 個の駅があり，それぞれ 1, 2, \ldots, N の番号が付けられている．また，M 本の鉄道路線があり，それぞれ 1, 2, \ldots, M の番号が付けられている．鉄道路線 i (1 \leqq i \leqq M) は駅 A_i と駅 B_i を双方向に結んでおり，乗車運賃は C_i 円である．

JOI 君は駅 S の近くに住んでおり，駅 T の近くの IOI 高校に通っている．そのため，両者を結ぶ定期券を購入することにした．定期券を購入する際には，駅 S と駅 T の間を最小の運賃で移動する経路を一つ指定しなければならない．この定期券を用いると，指定した経路に含まれる鉄道路線は双方向に自由に乗り降りできる．

JOI 君は，駅 U および駅 V の近くにある書店もよく利用している．そこで，駅 U から駅 V への移動にかかる運賃ができるだけ小さくなるように定期券を購入したいと考えた．

駅 U から駅 V への移動の際は，まず駅 U から駅 V への経路を 1 つ選ぶ．この経路に含まれる鉄道路線 i において支払うべき運賃は，

• 鉄道路線 i が定期券を購入する際に指定した経路に含まれる場合，0 円
• 鉄道路線 i が定期券を購入する際に指定した経路に含まれない場合，C_i 円

となる．この運賃の合計が，駅 U から駅 V への移動にかかる運賃である．定期券を購入する際に指定する経路をうまく選んだときの，駅 U から駅 V への移動にかかる運賃の最小値を求めたい．

課題

定期券を購入する際に指定する経路をうまく選んだときの，駅 U から駅 V への移動にかかる運賃の最小値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq S \leqq N．
• 1 \leqq T \leqq N．
• 1 \leqq U \leqq N．
• 1 \leqq V \leqq N．
• S \neq T．
• U \neq V．
• S \neq U または T \neq V．
• どの駅から他のどの駅へも 1 本以上の鉄道路線を用いて到達できる．
• 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)．
• 1 \leqq i < j \leqq M に対し，A_i \neq A_j または B_i \neq B_j．
• 1 \leqq Ci \leqq 1\,000\,000\,000 (1 \leqq i \leqq M)．

小課題

小課題 1 [16 点]

• S = U を満たす．

小課題 2 [15 点]

• 駅 S から駅 T へ最小の運賃で移動するときに用いることができる経路は 1 通りしかない．

小課題 3 [24 点]

• N \leqq 300 を満たす．

小課題 4 [45 点]

• 追加の制限はない．

入力例 1

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

出力例 1

2

この入力例では，定期券を買う際に指定できる経路は駅 1 → 駅 2 → 駅 3 → 駅 5 → 駅 6 という経路に限られる．

駅 1 から駅 4 への移動にかかる運賃を最小化するには，駅 1 → 駅 2 → 駅 3 → 駅 5 → 駅 4 という経路を選べばよい．この経路を選んだ場合，各鉄道路線において支払うべき運賃は，

• 駅 4 と駅 5 を結ぶ鉄道路線 5 においては，2 円．
• それ以外の鉄道路線においては，0 円．

となるので，かかる運賃の合計は 2 円となる．

入力例 2

6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

出力例 2

3000000000

この入力例では，駅 3 から駅 6 への移動に定期券を用いない．

入力例 3

8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8

出力例 3

15

入力例 4

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

出力例 4

0

入力例 5

10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16

出力例 5

19

JOI 研究所では 2^L 匹の毒蛇を飼っており，それぞれ 0, 1, \ldots, 2^L - 1 の番号が付けられている．すべての毒蛇は頭から順に L 個の部分に分かれており，それぞれの部分は青または赤である．毒蛇 i に対し，i を 2 進表記して i = \sum_{k = 1}^{L} c_k 2^{L - k} (0 \leqq c_k \leqq 1) とおいたとき，

• c_k = 0 であれば，毒蛇 i の頭から数えて k 番目の部分は青であり，
• c_k = 1 であれば，毒蛇 i の頭から数えて k 番目の部分は赤である．

各毒蛇には毒性と呼ばれる 0 以上 9 以下の整数値が定まっている．0，1，2，3，4，5，6，7，8，9 からなる長さ 2^L の文字列 S が与えられ，その i 文字目 (1 \leqq i \leqq 2^L) は毒蛇 i - 1 の毒性を表す．

毒蛇たちの動きは素早いので，JOI 研究所からは，よく毒蛇たちが脱走してしまう．JOI 研究所には脱走した毒蛇を目撃した周辺住民から苦情が寄せられる．

あなたには，Q 日間にわたる苦情の情報が与えられる．d 日目 (1 \leqq d \leqq Q) に寄せられた苦情は 0，1，? からなる長さ L の文字列 T_d として表され，

• T_d の j 文字目 (1 \leqq j \leqq L) が 0 の場合は，d 日目に脱走したすべての毒蛇の頭から数えて j 番目の部分が青であることを表し，
• T_d の j 文字目 (1 \leqq j \leqq L) が 1 の場合は，d 日目に脱走したすべての毒蛇の頭から数えて j 番目の部分が赤であることを表し，
• T_d の j 文字目 (1 \leqq j \leqq L) が ? の場合は，d 日目に脱走した毒蛇の頭から数えて j 番目の部分については，周辺住民からは情報が与えられなかったことを表す．

苦情はすべて正確な情報である．脱走した毒蛇は JOI 研究所の職員がその日のうちに捕獲する．捕獲された毒蛇が，翌日以降に再び脱走することはあり得る．

毒蛇の脱走によるリスクを見積もるために，JOI 研究所の K 理事長は脱走した可能性のある毒蛇の毒性の合計を知りたい．あなたの仕事は，Q 日間にわたる苦情の情報から，それぞれの日ごとに，その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成することである．

課題

毒蛇の毒性を表す文字列 S と，Q 日間の苦情の情報が与えられるので，それぞれの日ごとに，その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成せよ．

メモリ制限が小さいことに注意すること．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq L \leqq 20．
• 1 \leqq Q \leqq 1\,000\,000．
• S は長さ 2^L の文字列である．
• 文字列 S は 0，1，2，3，4，5，6，7，8，9 からなる．
• T_d は長さ L の文字列である (1 \leqq d \leqq Q)．
• 文字列 T_d は 0，1，? からなる (1 \leqq d \leqq Q)．

小課題

小課題 1 [5 点]

以下の条件を満たす．

• L \leqq 10．
• Q \leqq 1 000．

小課題 2 [7 点]

• L \leqq 10 を満たす．

小課題 3 [10 点]

• L \leqq 13 を満たす．

小課題 4 [53 点]

• Q \leqq 50 000 を満たす．

小課題 5 [25 点]

• 追加の制限はない．

入力例 1

3 5
12345678
000
0??
1?0
?11
???

出力例 1

1
10
12
12
36

この入力例では，L = 3 である．3 つの部分に分かれた毒蛇が，全部で 2^3 = 8 匹いる．苦情は 5 日間にわたって寄せられる．

• 1 日目に脱走した可能性のある毒蛇は，毒蛇 0 のみである．毒性の合計は 1 である．
• 2 日目に脱走した可能性のある毒蛇は，毒蛇 0, 1, 2, 3 である．毒性の合計は 10 である．
• 3 日目に脱走した可能性のある毒蛇は，毒蛇 4, 6 である．毒性の合計は 12 である．
• 4 日目に脱走した可能性のある毒蛇は，毒蛇 3, 7 である．毒性の合計は 12 である．
• 5 日目に脱走した可能性のある毒蛇は，毒蛇 0, 1, 2, 3, 4, 5, 6, 7 である．毒性の合計は 36 である．

入力例 2

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

出力例 2

9
18
38
30
14
15
20
80