問題文

AtCoder Land は、 10 時ちょうど、 15 時ちょうど、 17 時ちょうどの 3 つのタイミングでしか入場できません。

高橋君は X 時ちょうどに AtCoder Land に到着しました。最短で何時ちょうどに入園できますか？
但し、高橋君の到着と同じタイミングに AtCoder Land に入場できる場合も、高橋君は AtCoder Land に入場できるものとします。

制約

• X は 6 \le X \le 17 を満たす整数

入力例 1

14

出力例 1

15

高橋君は 14 時ちょうどに AtCoder Land に到着しました。高橋君は 15 時ちょうどに入園できます。

入力例 2

17

出力例 2

17

高橋君は 17 時ちょうどに AtCoder Land に到着しました。高橋君は 17 時ちょうどに入園できます。
この入力は、高橋君の到着と同じタイミングに AtCoder Land に入場できる場合に対応します。

入力例 3

6

出力例 3

10

問題文

AtCoder Land では時報がモールス信号で行なわれます。高橋君はこのモールス信号を解読したいです。

N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。S_i (1 \leq i \leq N) は . と - からなる文字列で、0 以上 9 以下のある数字に対応するモールス符号です。N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。

数字とモールス符号の対応は以下の通りです。

0 -----
1 .----
2 ..---
3 ...--
4 ....-
5 .....
6 -....
7 --...
8 ---..
9 ----.

制約

• 1 \leq N \leq 100
• N は整数
• S_i (1 \leq i \leq N) は . と - からなる文字列
• S_i (1 \leq i \leq N) は 0 以上 9 以下のある数字に対応するモールス符号

入力例 1

3
...--
.....
---..

出力例 1

358

...-- は 3 と、..... は 5 と、---.. は 8 と復号されます。よって、358 を出力します。

入力例 2

10
-----
.----
..---
...--
....-
.....
-....
--...
---..
----.

出力例 2

0123456789

問題文

高橋君は AtCoder Land にある屋外アトラクションに K 回乗ろうとしています。このアトラクションの一回の所要時間は T です。

現在の時刻は 0 です。時刻 0 から N までの降水量が与えられます。時刻 i から時刻 i+1 までの降水量は P_i です (0\leq i\lt N)。アトラクションには時刻 0,1,…,N−T に乗ることができます。時刻 t にアトラクションに乗ると時刻 t+T にアトラクションから降りることができ、アトラクションに乗っている間に P_t+P_{t+1}+\dots+P_{t+T-1} だけ濡れます。

高橋君はアトラクションに乗っている間にできるだけ雨に濡れないようにしたいです。時刻 N までに K 回アトラクションに乗るとき、高橋君が濡れる量の総和の最小値を求めてください。ただし、乗り換えにかかる時間や待ち時間は 0 とし、アトラクションから降りた時刻に新たにアトラクションに乗ることができるものとします。

制約

• 1\leq N\leq 2\times 10^5
• 1\leq K\leq \min(N,100)
• 1\leq T\leq N/K
• 0\leq P_i\leq 10^{9}
• 入力は全て整数

入力例 1

8 3 2
3 5 10 4 1 7 3 9

出力例 1

23

次のようにアトラクションに 3 回乗ることで濡れる量を合計で 23 にすることができ、これが最小です。

• アトラクションに時刻 0 に乗り、時刻 2 に降りる。この間に P_0+P_1=3+5=8 濡れる。
• アトラクションに時刻 3 に乗り、時刻 5 に降りる。この間に P_3+P_4=4+1=5 濡れる。
• アトラクションに時刻 5 に乗り、時刻 7 に降りる。この間に P_5+P_6=7+3=10 濡れる。

入力例 2

5 1 3
1000 1 10000 100 10

出力例 2

10101

入力例 3

15 5 2
401054171 63773035 986525245 157986893 799814573 139201145 649233932 351289844 409065258 406122133 957285954 529460482 21179081 795984182 727882733

出力例 3

3522058414

問題文

AtCoder Land には N 個の地点と M 個の道があります。i 個目の道は地点 a_i と b_i を双方向に結び、通過するのに d_i 分かかります。

これから、AtCoder Land で K 個のイベントが開催されます。i 個目のイベントに参加するには、時刻 t_i 分に地点 c_i にいる必要があります。イベントにかかる時間は 0 分です。

あなたは、時刻 0 分に地点 1 にいます。適切に行動したとき、最大で何個のイベントに参加できるか求めてください。

制約

• 1 \leq N \leq 1000
• 0 \leq M \leq 1000
• 1 \leq K \leq 1000
• 1 \leq a_i < b_i \leq N
• i \neq j なら (a_i, b_i) \neq (a_j, b_j)
• 1 \leq d_i \leq 10^9
• 1 \leq c_i \leq N
• 1 \leq t_i \leq 10^9
• i \neq j なら (c_i,t_i) \neq (c_j,t_j)
• 入力はすべて整数

入力例 1

3 3 3
1 2 1
1 3 3
2 3 7
1 8
2 2
3 7

出力例 1

2

たとえば、次のように行動することで、2 つのイベントに参加することができます。

• はじめ、時刻 0 分に地点 1 にいる
• 道 1 を通って時刻 1 分に地点 2 に到着する
• 時刻 2 分に地点 2 でイベント 2 に参加する
• 道 1 を通って時刻 3 分に地点 1 に到着する
• 道 2 を通って時刻 6 分に地点 3 に到着する
• 時刻 7 分に地点 3 でイベント 3 に参加する

3 つ以上のイベントに参加することはできないので、答えは 2 です。

入力例 2

1 0 2
1 1
1 100

出力例 2

2

道が存在しないため、地点 1 から動くことはできませんが、地点 1 で開催される 2 つのイベントに参加することができます。

入力例 3

5 8 10
1 2 149622151
1 4 177783960
4 5 118947237
1 3 33222944
1 5 295060863
3 5 110881471
2 3 34104208
3 4 273071547
2 650287940
4 839296263
3 462224593
1 492601449
4 384836991
1 191890310
5 576823355
3 782177068
3 404011431
1 818008580

出力例 3

6

問題文

高橋くん一行は、AtCoder Land に行くためにランド内にあるホテルに泊まることにしました。

N 人の人と M 個のランクが付いた部屋があります。

i 番目の人はランクが A_i 以上の部屋に泊まりたいと考えています。

また、i 番目の部屋のランクは R_i、定員は B_i 人、客室料金は C_i 円です。 C_i 円払うことで、B_i 人以下であれば何人でも i 番目の部屋に泊まることができます。

N 人全員が部屋に泊まることが可能か判定し、可能な場合必要な金額の総和の最小値を求めてください。

制約

• 1\leq N,M \leq 5000
• 1\leq A_i,R_i,B_i,C_i \leq 5000
• 入力は全て整数

入力例 1

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

出力例 1

4

1 番目の人が 2 番目の部屋に泊まり、それ以外の人が 1 番目の部屋に泊まることを考えます。

このとき必要な金額の総和は 4 となり、これが最小であることが示せます。

入力例 2

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

出力例 2

11

入力例 3

10 1
1 1 1 1 1 1 1 1 1 1
10 4 1

出力例 3

-1

N 人全員が部屋に泊まることはできません。

問題文

AtCoder Land で高橋君と青木君はイチゴの乗ったケーキを食べることになりました。

AtCoder Landのケーキは円形で、N 個の半径方向の切れ込みによって N 個の扇形ピースに区切られています。

切れ込みを時計回りの順に切れ込み 1, 切れ込み 2, \ldots, 切れ込み N と番号をふったとき、時計回りに切れ込み i (1 \leq i \leq N-1) から切れ込み i+1 までの間の部分をピース i と呼びます。また、時計回りに切れ込み N から切れ込み 1 までの間の部分をピース N と呼びます。

ピース i (1 \leq i \leq N) の上には A_i 個のイチゴが乗っています。

高橋君と青木君はこれから以下のゲームをします。

• まず、高橋君が N 個の切れ込みのなかから 1 つを選ぶ。選んだ切れ込みを切れ込み i とする。
• 次に、青木君が高橋君の選んだ切れ込み以外の N-1 個の切れ込みのなかから 1 つを選ぶ。選んだ切れ込みを切れ込み j とする。
• 高橋君は切れ込み i から時計回りに見ていって、切れ込み j までの範囲のピースをすべてもらう。
• 青木君は、残りのピースをすべてもらう。
• 高橋君がもらったピースの 1 ピースあたりのイチゴの個数の平均値が青木君がもらったピースの 1 ピースあたりのイチゴの個数の平均値以上であるとき、高橋君の勝ちです。そうでないとき、青木君の勝ちです。

青木君が勝つために最適な切れ込みを選ぶとき、高橋君は必ず勝つためにはどの切れ込みを選べばよいか求めてください。そのような切れ込みが、存在しないときは -1 を、複数存在する場合はそのうち番号が最小のものを答えてください。

制約

• 2 \leq N \leq 5 \times 10^{5}
• 0 \leq A_i \leq 5 \times 10^{5}
• 入力は全て整数

入力例 1

3
3 8 5

出力例 1

2

高橋君が切れ込み 1 を選んだ時、青木君は切れ込み 2 を選ぶと高橋君はピース 1 のみを、青木君はピース 2,3 をもらいます。高橋君のもらったピースの上に乗ってるイチゴの個数の平均値は 3、青木君のもらったピースの上に乗ってるイチゴの個数の平均値は 6.5 です。よって青木君が勝ちます。

高橋君が切れ込み 2 を選んだ時、青木君はどの切れ込みを選んでも高橋君が勝ちます。よって、答えは 2 です。

入力例 2

15
4096 64 512 1 256 16384 8 1024 2048 2 128 32 4 16 8192

出力例 2

15

問題文

高橋くん一行は、AtCoder Land 内のアイス屋さんにやってきました。

アイス屋さんには N 種類のフレーバーのアイスがあり、アイスはそれぞれ十分な量の在庫があります。

このアイス屋さんでは、5 段重ねのアイスを購入することができます。 使う 5 つのフレーバーは（重複も含めて）自由に選ぶことができますが、あるアイスの上に直接同じ味のアイスを重ねることはできません。 つまり、このアイス屋さんで購入できる 5 段重ねのアイスは N\times(N-1) ^ 4 通りあります。

高橋くんはこのアイス屋さんのクーポンを持っており、i=1,2,\ldots,N すべてに対して i 番目のフレーバーのアイスを注文した数が C _ i 個以下なら、クーポンを使って購入することができます。 売られているアイスの定価は非常に高いため、高橋くんはクーポンを使って購入できる個数を超えてアイスを購入することはできません。

高橋くんは、なるべく多くの友達に 5 段重ねのアイスを買ってあげたいと思っています。 5 段重ねのアイスを最大でいくつ買うことができるか求め、それを実現するアイスの注文をひとつ構成してください。

厳密には、次のようになります。

次の条件をすべて満たす K\times5 項の列 (A _ {i,j}) _ {1\leq i\leq K,1\leq j\leq 5} が存在するような非負整数 K の最大値を求め、その K に対する具体的な (A _ {i,j}) をひとつ構成してください。

• 1\leq A _ {i,j}\leq N\ (1\leq i\leq K,1\leq j\leq 5)
• A _ {i,j}\neq A _ {i,j+1}\ (1\leq i\leq K,1\leq j\leq 4)
• x=1,2,\dotsc,N に対して、A _ {i,j}=x となる組 (i,j) の個数は C _ x 個以下

ただし、条件を満たす (A _ {i,j}) が複数存在する場合、どれを出力しても構いません。

制約

• 1\leq N\leq2\times10 ^ 5
• 0\leq C _ i\leq2\times10 ^ 5
• \displaystyle\sum _ {i=1} ^ NC _ i\leq2\times10 ^ 5
• 入力はすべて整数

入力例 1

5
3 1 4 2 5

出力例 1

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

次のようにすることで、5 段重ねのアイスを 3 つ買うことができます。

例えば、次のように出力しても正解になります。

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

逆に、次のような出力は正解と判定されません。

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

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

2
1 2 3 4 5
1 3 4 5 1

それぞれ、あるアイスの上に直接同じフレーバーを乗せているため、2 番と 4 番のフレーバーを購入できる個数を超えて注文しているため、K が最大ではないためです。

入力例 2

3
1 2 1000

出力例 2

1
3 1 3 2 3

高橋くんはアイス 1003 個ぶんのクーポンを持っていますが、5 段重ねのアイスは 1 つしか買うことができません。

入力例 3

1
3

出力例 3

0

5 段重ねのアイスを 1 つも買うことができない場合もあります。

入力例 4

10
2 1 8 6 1 2 1 6 9 1

出力例 4

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

問題文

AtCoder Land には N 個のアトラクションがあります。
i 番目のアトラクションには、以下の 2 通りの搭乗方法があります。

• 通常通り搭乗する。
  • A_i 分後に搭乗が終了する。
• ファストパスを使って搭乗する。
  • B_i 分後に搭乗が終了する。このとき、ファストパスが 1 枚消費される。

あなたはファストパスを K 枚持っています。
同じアトラクションに複数回搭乗しないものとすると、 T 分後までに最大でいくつのアトラクションに搭乗できますか？
但し、アトラクションを乗り換える時間は無視できること、最後に搭乗するアトラクションについて T 分後までに搭乗が終了している必要があることに注意してください。

制約

• 入力は全て整数
• 1 \le K \le N \le 2 \times 10^5
• 1 \le T \le 10^{18}
• 1 \le B_i \le A_i \le 10^{12}

入力例 1

5 2 20
7 4
10 8
3 3
8 7
9 5

出力例 1

4

この入力において AtCoder Land には 5 個のアトラクションがあり、あなたはファストパスを 2 枚持っています。

• まず、 5 番目のアトラクションにファストパスを使って搭乗する。
  • このとき、 5 分後に搭乗が終了し、ファストパスの残りは 1 枚になります。 全体で 5 分経過しています。
• 次に、 3 番目のアトラクションに通常通り搭乗する。
  • このとき、 3 分後に搭乗が終了します。 全体で 8 分経過しています。
• 次に、 1 番目のアトラクションにファストパスを使って搭乗する。
  • このとき、 4 分後に搭乗が終了し、ファストパスの残りは 0 枚になります。 全体で 12 分経過しています。
• 最後に、 4 番目のアトラクションに通常通り搭乗する。
  • このとき、 8 分後に搭乗が終了します。 全体で 20 分経過しています。

以上の通りにすると 4 つのアトラクションに搭乗でき、これが最大であることが証明できます。

入力例 2

5 5 1
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000

出力例 2

0

T 分以内にひとつもアトラクションに搭乗できない場合もあります。

入力例 3

5 5 1000000000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000

出力例 3

5

T 分以内に全てのアトラクションに搭乗できる場合もあります。

入力例 4

15 4 60
9 4
8 8
10 10
7 6
10 3
6 6
8 7
9 5
6 5
4 2
1 1
7 6
8 6
6 4
4 3

出力例 4

12