問題文

プリンセスの高橋さんは、舞踏会に着ていくドレスを選んでいます。

高橋さんは N 着のドレスを持っています。 i 番目のドレスの色は C_i、華やかさは A_i です。

舞踏会にはドレスコードがあり、色が X のドレスだけを着ることができます。

高橋さんが着ることのできるドレスの華やかさの最大値を出力してください。ただし、着ることのできるドレスを一着も持っていない場合は、-1 を出力してください。

制約

• 1 \le N \le 100
• 1 \le C_i,X \le 100
• 1 \le A_i \le 100
• 入力はすべて整数である

入力例 1

5 2
1 10
2 30
2 25
3 100
2 40

出力例 1

40

2, 3, 5 番目のドレスは色が 2 です。それぞれ華やかさは 30,25,40 であるため、最大値は 40 です。

入力例 2

3 4
1 20
2 40
3 60

出力例 2

-1

色が 4 のドレスを一着も持っていないため、-1 を出力します。

入力例 3

12 2
1 10
2 30
2 25
3 100
2 40
4 80
5 60
2 90
1 70
3 50
2 65
4 99

出力例 3

90

問題文

プリンセスの高橋さんは、T 秒間のバレエの演目を練習しています。

高橋さんは 1 秒ごとに、左足と右足を独立に浮かせるか地面につけるかを選べます。ただし、K+1 秒以上連続で両足を浮かせることはできません。

演目には、足の動かし方について次の N+M 個の指示があります。

• 各 i\ (1\le i\le N) について、L_i 秒目に左足を浮かせる
• 各 i\ (1\le i\le M) について、R_i 秒目に右足を浮かせる

指示された秒に指示された足を浮かせているならば、その指示を満たしたものとします。

満たすことのできる指示の個数の最大値を求めてください。

制約

• 1 \le N,M \le 2 \times 10^5
• 1 \le K \le T \le 10^9
• 1 \le L_1 \lt L_2 \lt \cdots \lt L_N\le T
• 1 \le R_1 \lt R_2 \lt \cdots \lt R_M\le T
• 入力はすべて整数である

入力例 1

3 3 5 1
1 2 3
2 3 5

出力例 1

5

例えば、左足を 1, 2, 3 秒目、右足を 2, 5 秒目に浮かせれば「3 秒目に右足を浮かせる」を除いた 5 個の指示を満たせます。

このとき、加えて 3 秒目に右足を浮かせることはできません。なぜなら 2, 3 秒目の 2 ~ ( = K+1) 秒連続で両足を浮かせることになるためです。

入力例 2

7 7 10 2
1 2 3 4 5 6 7
1 2 3 4 5 6 7

出力例 2

12

左足を 1,2,3,4,5,6,7,10 秒目、右足を 1,2,4,5,7 秒目に浮かせれば 12 個の指示を満たせます。

また、指示のない秒に足を浮かせても構いません。

入力例 3

10 9 15 2
1 2 3 4 7 8 9 11 14 15
2 3 4 6 7 8 9 12 15

出力例 3

17

問題文

プリンセスの高橋さんは、戴冠式でかぶる王冠を作っています。

王冠には、宝石を取り付ける場所が円形に K 個並んでいます。また、宝石は N 個あり、i 番目の宝石の色は C_i、価値は V_i です。

N 個の宝石から異なる K 個の宝石を選び、それぞれの場所に 1 つずつ取り付けます。ただし、美しさのために、以下のルールを守らなければなりません。

• 隣り合う場所に、同じ色の宝石を取り付けてはいけない

取り付けた宝石の価値の合計として考えられる最大値を求めてください。ただし、条件を満たす取り付け方が存在しない場合は -1 を出力してください。

制約

• 3 \le K \le N \le 2 \times 10 ^ 5
• 1 \le C_i \le N
• 1 \le V_i \le 10^9
• 入力はすべて整数である

入力例 1

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

出力例 1

30

1, 2, 3, 4 番目の宝石を順に取り付けることにすると ( 色, 価値 ) が (1, 10),(2, 8),(1, 7),(3, 5) の順に並びます。このとき、価値の合計は 30 です。

入力例 2

5 5
1 10
1 9
1 8
2 7
2 6

出力例 2

-1

条件を満たすように 5 個の宝石を取り付けることはできません。王冠は円形であることに注意をしてください。

入力例 3

12 8
1 10
1 7
1 6
1 1
2 9
2 8
2 3
3 11
3 5
3 4
4 2
5 12

出力例 3

68

問題文

プリンセスの高橋さんは武道を習うつもりでしたが、間違えて葡萄の教室に来てしまいました。

N 段にわたって、ブドウの粒が三角形状に並んでいます。上から i 段目には N-i+1 個の粒があり、左から j 番目の粒を (i,j) と表します。

粒 (i,j) と、次に挙げる粒は、その座標が存在するとき隣り合っています。

• (i,j-1),(i,j+1)
• (i-1,j),(i-1,j+1)
• (i+1,j-1),(i+1,j)

たとえば N = 4 のときは下図のようになっています。

高橋さんは、隣り合う 2 粒を選んで食べる操作を繰り返します。一度食べた粒を再び選ぶことはできません。

行うことのできる操作回数の最大値を求め、その回数の操作方法を 1 つ出力してください。

制約

• 1 \le N \le 1000
• 入力はすべて整数である

入力例 1

3

出力例 1

3
1 1 1 2
1 3 2 2
3 1 2 1

ブドウは 6 粒あります。図のように組にして、すべての粒を一度ずつ選ぶことで 3 回の操作を行えます。

入力例 2

2

出力例 2

1
1 2 2 1

ブドウは 3 粒あります。1 粒は食べることができません。

入力例 3

4

出力例 3

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

問題文

プリンセスの高橋さんは、バイオリンの練習をしています。

高橋さんのバイオリンには N 本の弦があります。i 番目の弦を使うと、周波数が L_i 以上 R_i 以下の実数である任意の音を出すことができます。

高橋さんは、お腹が空いたので弦を 0 本以上選んで食べることにしました。食べた弦は無くなります。ただし、バイオリンを壊したくはないため、以下の条件は守らなくてはいけません。

• 弦を食べる前に出すことのできたすべての周波数の音は、弦を食べた後にも出すことができる

食べることのできる弦の本数の最大値を求めてください。

制約

• 1 \le N \le 2 \times 10 ^ 5
• 1 \le L_i \le R_i \le 10^9
• 入力はすべて整数である

入力例 1

3
1 4
2 4
3 6

出力例 1

1

(L_2, R_2) = (2,4) の音を出せる弦を食べても、その範囲の音はほかの弦によって出すことができます。よって答えは 1 です。

入力例 2

3
1 2
2 3
3 4

出力例 2

0

周波数は任意の実数について考えることに注意してください。例えば、 2 番目の弦を食べると周波数が 2.5 の音を出すことができなくなるため、食べることはできません。

入力例 3

15
1 10
2 3
4 5
6 9
1 6
20 25
24 30
20 22
23 27
26 30
21 29
40 40
40 40
50 52
52 55

出力例 3

9

問題文

プリンセスの高橋さんは、ピアノの練習をしています。

ピアノには N 個の鍵盤があり、左から順に 1,2,\ldots,N と番号が付いています。高橋さんには A 本の腕があり、それぞれの腕には B 本の指があります。各指は高々 1 個の鍵盤を押すことができます。

ただし、同じ腕にある指で押すどの 2 つの鍵盤についても、その番号の差は D 以下でなければなりません。

N 個の鍵盤から異なる K 個を選ぶ選び方であって、選んだすべての鍵盤を同時に押すことのできるものの個数を 998244353 で割った余りを求めてください。ただし、どの腕・どの指を使うかが異なっていても、選んだ鍵盤が同じなら同じ選び方とみなします。

制約

• 2 \le N \le 100
• 1 \le K \le N
• 1 \le A,B \le 10
• 1 \le D \le N-1
• 入力はすべて整数である

入力例 1

5 2 1 2 2

出力例 1

7

鍵盤の選び方として (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5) の 7 通りが条件を満たします。

入力例 2

5 5 2 2 4

出力例 2

0

指の本数は合計 4 本であるため、5 個の鍵盤を同時に押すことはできません。

入力例 3

20 7 4 3 5

出力例 3

77520

入力例 4

100 50 10 6 7

出力例 4

591911044

問題文

プリンセスの高橋さんは乗馬をしようとしましたが、間違えて競馬場に来てしまいました。

競馬場では、N 頭の馬がレースに出走します。馬には、単勝での人気が高い順に 1,2,\ldots,N の番号が付いています。

N 頭の馬から異なる K 頭を選び、その番号を昇順に並べた列 (a_1,a_2,\ldots,a_K) を考えます。このような列 \displaystyle\binom{N}{K} 個に、 1 位から \displaystyle\binom{N}{K} 位までの相異なる順位を付けます。

順位の付け方は、次の条件を満たさなければなりません。

• 異なる 2 つの列 a=(a_1,a_2,\ldots,a_K),~ b=(b_1,b_2,\ldots,b_K) が、すべての i\ (1\le i\le K) について a_i\le b_i を満たすならば、a の順位は b の順位よりも小さい。

条件を満たすすべての順位の付け方を考えます。与えられた列 (x_1,x_2,\ldots,x_K) の順位としてあり得る最小値と最大値を求め、それぞれを 998244353 で割った余りを出力してください。

制約

• 1 \le K \le N \le 10^9
• K \le 300
• 1 \le x_1 \lt x_2 \lt \cdots \lt x_K\le N
• 入力はすべて整数である

入力例 1

4 2
2 4

出力例 1

5 5

全部で \binom{4}{2} = 6 個の列に順位をつけます。(2, 4) と比べた時、(1, 2), (1, 3), (1, 4), (2, 3) は必ず順位が小さく、(3, 4) は必ず順位が大きいです。 よって順位は最小・最大ともに 5 です。

入力例 2

4 2
2 3

出力例 2

3 4

全部で \binom{4}{2} = 6 個の列に順位をつけます。(2, 3) と比べた時、(1, 2), (1, 3) は必ず順位が小さく、(2, 4), (3, 4) は必ず順位が大きいです。(1, 4) は順位を小さくすることも、大きくすることも可能です。よって順位は最小が 3、最大は 4 です。

入力例 3

20 7
2 3 5 7 11 13 17

出力例 3

2217 39247

入力例 4

20260801 8
2 20 202 2026 20260 202608 2026080 20260801

出力例 4

620426308 756016478

問題文

プリンセスの高橋さんは、森の中で迷子になってしまいました。

森には N 個の広場と M 本の道があります。広場には 1 から N までの番号が付いています。道 i は広場 a_i と広場 b_i を双方向に結んでおり、幅は c_i、長さは d_i です。複数の道が同じ広場の組を結ぶこともあります。また、どの広場からどの広場へもいくつかの道を通って到達することができます。

森には K 匹の動物がいます。動物 j は、はじめ広場 v_j にいて、大きさは x_j です。大きさが x の動物は、幅が x 以上の道だけを通ることができます。

高橋さんは、はじめ広場 1 にいて、動物には乗っていません。高橋さんは次の行動を好きな回数行えます。

• 動物に乗っていないとき、道を 1 本選んで歩いて移動する。このとき、歩行距離はその道の長さだけ増える。
• 動物に乗っていないとき、同じ広場にいる動物に乗る。
• 動物に乗っているとき、その動物が通れる道を 1 本選び、動物とともに移動する。このとき、歩行距離は増えない。
• 動物に乗っているとき、その動物から降りる。動物はその広場に残る。

高橋さんは道の幅によらず、どの道でも歩くことができます。また、道の途中で止まったり、動物に乗り降りしたりすることはできません。動物は、高橋さんが乗って移動するとき以外には移動しません。

広場 N に到達するまでの歩行距離の最小値を求めてください。

制約

• 2 \le N \le 10^5
• N-1 \le M \le 10^5
• 1 \le K \le 10^5
• 1 \le a_i \lt b_i\le N
• 1 \le c_i,d_i\le 10^9
• 1 \le v_j \le N
• 1 \le x_j \le 10^9
• 与えられるグラフは連結である
• 入力はすべて整数である

入力例 1

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

出力例 1

3

以下のようにすれば、歩行距離が 3 となります。

• 広場 1 から道 1 を用いて広場 2 まで歩く。歩行距離は 3 となる。
• 広場 2 で動物 1 に乗る。
• 動物に乗ったまま、広場 2 から道 2 を用いて広場 3 に行く。
• 動物に乗ったまま、広場 3 から道 3 を用いて広場 4 に行く。

入力例 2

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

出力例 2

7

以下のようにすれば、歩行距離が 7 となります。

• 広場 1 で動物 1 に乗る。
• 動物に乗ったまま、広場 1 から道 1 を用いて広場 2 に行く。
• 広場 2 で動物から降りる。動物 1 は広場 2 に残る。
• 広場 2 から道 2 を用いて広場 3 まで歩く。歩行距離は 7 となる。

道 2 は幅 2 ですから、大きさが 5 の動物 1 は通ることができないことに注意してください。

入力例 3

15 14 3
1 2 9 8
2 3 9 8
3 4 9 8
4 5 9 8
5 6 5 8
6 7 5 8
7 8 5 8
8 9 5 8
9 10 5 8
10 11 2 8
11 12 2 8
12 13 2 8
13 14 2 8
14 15 2 8
1 9
5 5
10 2

出力例 3

0

入力例 4

10 19 5
1 2 594909233 622379185
2 3 725115453 486137434
3 4 227907877 347378973
4 5 35626222 730377835
3 6 819140532 653954484
1 7 790169806 729923705
4 8 127763929 356749837
8 9 62511885 377315779
6 10 537489942 409936741
1 7 628157873 35857198
1 10 936797035 549456204
5 10 640646299 921436478
4 9 410095318 333337850
5 10 42622736 890036373
2 10 904887490 856341412
6 7 413238445 652816775
9 10 437102059 490707900
2 10 500383136 189664736
1 4 714288343 489127699
8 62511886
10 437102060
8 127763929
10 936797035
6 413238445

出力例 4

549456204