問題文

ドワンゴ社の運営する動画サイトには n 本の動画があります。ニワンゴくんが検索してみたところ、そのうちタイトルに「ドワンゴ」を含む動画が a 本あり、「ニコニコ」を含む動画が b 本あることがわかりました。

ニワンゴくんは「ドワンゴ」「ニコニコ」の両方をタイトルに含む動画が何本あるのか気になっています。そのような動画は最低でも何本あると言えるでしょうか。

制約

• 1 ≦ n ≦ 14,000,000
• 1 ≦ a ≦ n, 1 ≦ b ≦ n

入力例 1

100 40 35

出力例 1

0

このケースでは、タイトルに「ドワンゴ」「ニコニコ」の両方を含む動画が 1 本もないことがありえます。たとえば 100 本ある動画のうち

• 40 本はタイトルに「ドワンゴ」を含むが「ニコニコ」は含まない。
• 35 本はタイトルに「ニコニコ」を含むが「ドワンゴ」は含まない。
• 25 本はタイトルに「ドワンゴ」「ニコニコ」のいずれも含まない。

といった場合が考えられます。

入力例 2

100 60 70

出力例 2

30

入力例 3

14000000 2458 692196

出力例 3

0

このコンテストの開催時 (2016年12月17日)、ニコニコ動画にある動画総数が約 14,000,000 件です。

問題文

ニコニコ文字列とは、25 を 0 回以上繰り返した文字列のことをいいます。たとえば 25 や 252525 や空文字列はニコニコ文字列ですが、123 や 225 はニコニコ文字列ではありません。

ある文字列 S がその連続した部分文字列として含む最長のニコニコ文字列の長さを S の ニコニコレベル といいます。 たとえば 52525, 25025, 12151 のニコニコレベルはそれぞれ 4, 2, 0 です。

ニワンゴくんは 0 から 9 の数字と ? からなる文字列 T を持っており、それぞれの ? を好きな数字に置き換えることで、数字のみからなる文字列 T' を作ろうとしています。ニワンゴくんが作ることのできる文字列 T' のニコニコレベルの最大値を求めて下さい。

制約

• 1 ≦ |T| ≦ 10^5
• T の文字は 0 から 9 の数字か ? のいずれかである。

入力例 1

12??567890

出力例 1

4

? を前から順に 5 と 2 に置き換えて 1252567890 とすると、2 文字目から 5 文字目が 2525 となり、ニコニコレベル 4 の文字列を作ることができます。

入力例 2

65?5?4?

出力例 2

2

入力例 3

314159265358979

出力例 3

0

25 が全く現れない文字列はニコニコレベル 0 になります。

入力例 4

2???5????

出力例 4

8

入力例 5

52

出力例 5

0

問題文

スキーが大好きなタカシくんは、ニコニコスキー場でリフト係のアルバイトを始めました。 このスキー場には搬器（いす）1 台あたりの定員が 4 人であるリフトが 1 基あり、ここにスキー客が 1 人から 4 人までのグループで並びに来ます。

ある日、リフトの待ち行列が長くなったことに困ったタカシくんは、スキー客にリフトの相乗りをしてもらおうと考えました。 タカシくんは、搬器が 1 台乗り場に着くごとに以下のような手順でスキー客のグループをその搬器に案内することにしました。

• 最初に、待ち行列の先頭にいるグループを搬器に案内する。
• 現在の搬器に相乗りしても定員を超えないようなグループが存在する限り、そのようなグループを搬器に案内する。ただし、そのようなグループが複数存在する場合は、待ち行列での位置に関わらず、いずれのグループを案内しても構わない。

今、リフトには N グループのスキー客が並んでおり、待ち列の先頭から i (1 ≦ i ≦ N) 番目のグループは A_i 人のスキー客からなります。 タカシくんがうまくスキー客のグループを案内することによって、最短で何台目の搬器で今並んでいるグループをすべて運びきることができるかを求めて下さい。

制約

• 1≦N≦10^5
• 1≦A_i≦4

入力例 1

3
1
1
2

出力例 1

1

合計が 4 人以内であれば、タカシくんはグループを何組でも同じ搬器に案内することができます。

入力例 2

6
3
1
4
2
1
2

出力例 2

4

例えば以下のようにスキー客を案内すると 4 台の搬器で全てのグループを運びきることができます。

• 1 台目の搬器に 1 番目のグループと 5 番目のグループを案内する。
• 2 台目の搬器に 2 番目のグループと 4 番目のグループを案内する。
• 3 台目の搬器に 3 番目のグループを案内する。
• 4 台目の搬器に 6 番目のグループを案内する。

問題文

寿司が大好きなタカシくんは、回転寿司チェーン店のニコニコ寿司にやってきました。 タカシくんは寿司を食べることで幸福度を得ることができます。 しかし、タカシくんは現在糖質制限中で、普通に食べるよりもシャリを残してネタだけ食べる方が得られる幸福度が高くなります。

タカシくんが席に着くと、N 皿の寿司が順番に流れてきて、そのうちな好きな寿司を何皿でも取ることができます。 ただし、流れてくる順番でしか寿司を取ることができず、取った寿司を食べ終わってからしか次の寿司を取ることができません。 ここで、寿司を食べ終わるとは、寿司を普通に食べ終わるか、シャリを残してネタだけ食べ終わることを指します。 i (1≦i≦N) 番目に流れてきた寿司を、シャリを残してネタだけを食べた場合は幸福度を X_i 得ることができ、普通に食べた場合は幸福度を Y_i 得ることができます。

テーブルには、横に並べたときに M 皿まで置ける広さのスペースがあり、タカシくんは寿司を食べ終わるたびにここに皿を置いていきます。 すでに置いてある皿の上には別の皿を何枚でも重ねることができます。 しかし、ネタだけ食べた皿にはシャリが残っているため、その上に別の皿を重ねることはできません。 また、すでに置いてある皿の下に皿を置くことはできません。 皿を置ける場所がなくなった時点で、それ以上寿司を食べることはできません。

タカシくんが得ることのできる幸福度の合計の最大値を答えてください。

制約

• 1≦N≦10^5
• 1≦M≦10^5
• 1≦Y_i \lt X_i≦1,000

入力例 1

4 1
5 2
5 3
100 50
5 1

出力例 1

105

1,2 番目の寿司を普通に食べ、3 番目の寿司のネタだけを食べると得られる幸福度が 105 となり、これが最大です。 このとき、4 番目の寿司のように取らない寿司があっても構わないことに注意して下さい。

入力例 2

5 2
5 2
100 50
5 3
5 1
100 3

出力例 2

206

入力例 3

4 5
280 101
456 404
789 707
1000 999

出力例 3

2525

問題文

N + 2 枚の皿が一列に並んでいます。これらの皿を左から順に皿 0, 皿 1, ..., 皿 N+1 と番号づけます。皿 1 から皿 N までの N 枚の皿にはそれぞれ飴玉がいくつか乗っており、皿 0 と皿 N+1 には飴玉は乗っていません。

ニワンゴくんとニコニコテレビちゃんはこれらの飴玉を次のようにしてふたりで分けようとしています。

1. 皿 1 から皿 N までのそれぞれの皿について、その皿に乗っている飴玉をすべて左隣か右隣の皿へ移す。この移動は、各皿について左右の方向を決めたあとにすべて同時に行う。
2. 飴玉の乗っていない皿をすべて列から取り除く。
3. 残った皿のうち、左から奇数番目 (1, 3, 5, ... 番目) の皿に乗っている飴玉をニワンゴくんが、左から偶数番目 (2, 4, 6, ... 番目) の皿に乗っている飴玉をニコニコテレビちゃんがもらう。

ニワンゴくんはできるだけ多くの飴玉をもらえるように手順 1 での飴玉の移動方向を決めたいと思っています。ニワンゴくんのために、以下のようなプログラムを作って下さい。

最初、皿 i (1 ≦ i ≦ N) には A_i 個の飴玉が乗っているとします。その後、飴玉の個数を変化させるクエリが Q 個与えられるので順番に処理してください。j (1 ≦ j ≦ Q) 番目のクエリは 2 個の整数 K_j と X_j からなり、皿 K_j に乗っている飴玉の個数を X_j 個に変えることを表しています。

各 j (1 ≦ j ≦ Q) に対し、j 個目までのクエリを処理した状態からニワンゴくんとニコニコテレビちゃんが上記の方法で飴玉を分けるとき、ニワンゴくんがもらえる飴玉の個数の最大値を出力して下さい。

制約

• 1≦N≦5 \times 10^4
• 1≦A_i≦10^4
• 1≦Q≦5 \times 10^4
• 1≦K_j≦N
• 1≦X_j≦10^4

部分点

• Q=1 を満たすデータセットに正解した場合は、700 点が与えられる。

入力例 1

6
3 1 4 1 5 9
1
1 3

出力例 1

21

部分点の条件を満たすケースです。はじめ、皿に乗っている飴玉の個数は左の皿からそれぞれ 0, 3, 1, 4, 1, 5, 9, 0 です。

ここで、皿 1 から 6 について、乗っている飴玉をそれぞれ右・右・左・右・左・右隣の皿へと移すと、飴玉の個数は 0, 0, 7, 1, 5, 1, 0, 9 となります。

次に飴玉の乗っていない皿をすべて取り除くと 7, 1, 5, 1, 9 となり、左から奇数番目の皿に乗っている飴玉の合計個数は 21 となります。このケースではこれがニワンゴくんが最も多くの飴玉をもらえるパターンです。

入力例 2

5
1 2 3 4 5
1
1 1

出力例 2

11

部分点の条件を満たすケースです。

入力例 3

8
2 5 2 5 2 5 2 5
5
1 7
6 1
3 6
8 3
2 9

出力例 3

27
24
24
22
26

この入出力例は部分点の条件を満たしません。