問題

JOI 君は物理，化学，生物，地学，歴史，地理の 6 科目のテストを受けた．それぞれのテストは 100 点満点で採点された．

JOI 君は物理，化学，生物，地学の 4 科目から 3 科目を選択し，歴史，地理の 2 科目から 1 科目を選択する．

テストの合計点が最も高くなるように科目を選ぶとき，JOI 君の選んだ科目のテストの合計点を求めよ．

入力例 1

100
34
76
42
10
0

出力例 1

228

入出力例 1 では，JOI 君が物理，生物，地学，歴史の 4 科目を選ぶとき，テストの合計点が最高になる．
物理，生物，地学，歴史の点数はそれぞれ 100, 76, 42, 10 なので，選んだ科目のテストの合計点は 228 である．

入力例 2

15
21
15
42
15
62

出力例 2

140

入出力例 2 では，JOI 君が化学，生物，地学，地理の 4 科目を選ぶとき，テストの合計点が最高になる．
化学，生物，地学，地理の点数はそれぞれ 21, 15, 42, 62 なので，選んだ科目のテストの合計点は 140 である．
入出力例 2 では，JOI 君が物理，化学，地学，地理の 4 科目を選ぶ場合でも，選んだテストの合計点は 140 である．

問題

JOI 高校の N 人の生徒が東西に一列に並んでいる．列の西の端から i 番目の生徒が生徒 i である．それぞれの生徒は整数が 1 つ書かれたゼッケンを付けている．最初，生徒 i のゼッケンには整数 A_i が書かれている．

バトンが M 個あり，バトンには 1 から M までの番号が付けられている．k = 1, 2, \ldots, M に対し，以下の操作を行う．バトン k (2 \leqq k \leqq M) に関する操作は，バトン k - 1 に関する操作が終わってから行う．

1. 先生がバトン k を生徒 1 に渡す．
2. バトンを受け取った生徒は，以下のルールに従ってバトンを渡す．
   • ルール：生徒 i がバトン k を受け取ったとする．
     • 1 \leqq i \leqq N - 1 のとき: 生徒 i のゼッケンの整数を k で割った余りが，生徒 i + 1 のゼッケンの整数を k で割った余りよりも大きいとき，生徒 i と生徒 i + 1 がゼッケンを交換し，生徒 i は生徒 i + 1 にバトンを渡す．そうでないときは，ゼッケンを交換せずに，生徒 i は生徒 i + 1 にバトンを渡す．
     • i = N のとき: 生徒 N はバトンを先生に渡す．
3. 先生が生徒 N からバトン k を受け取ったら，バトン k に関する操作は終わりである．

生徒のゼッケンに最初に書かれていた整数とバトンの個数 M が与えられたとき，先生が生徒 N からバトン M を受け取った後の，それぞれの生徒のゼッケンの整数を求めるプログラムを作成せよ．

入力例 1

6 4
3
2
8
3
1
5

出力例 1

2
3
1
8
5
3

入出力例 1 では 6 人の生徒がいる．最初，生徒のゼッケンは順に 3, 2, 8, 3, 1, 5 である．バトンは 4 個ある．

• バトン 1 に関する操作が終了した時点での生徒のゼッケンは順に 3, 2, 8, 3, 1, 5 である．
• バトン 2 に関する操作が終了した時点での生徒のゼッケンは順に 2, 8, 3, 3, 1, 5 である．
• バトン 3 に関する操作が終了した時点での生徒のゼッケンは順に 2, 3, 3, 1, 8, 5 である．
• バトン 4 に関する操作が終了した時点での生徒のゼッケンは順に 2, 3, 1, 8, 5, 3 である．

入力例 2

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

出力例 2

6
1
2
3
10
4
8
7
9
5

問題

K 理事長はロシアで開催される IOI 2016 に合わせて旗を作ることにした．K 理事長はまず倉庫から古い旗を取り出してきた．この旗は N 行 M 列のマス目に分けられていて，それぞれのマスには白・青・赤のいずれかの色が塗られている．

K 理事長はこの旗のいくつかのマスを塗り替えてロシアの旗にしようとしている．ただし，この問題でいうロシアの旗とは以下のようなものである．

• 上から何行か（1 行以上）のマスが全て白で塗られている．
• 続く何行か（1 行以上）のマスが全て青で塗られている．
• それ以外の行（1 行以上）のマスが全て赤で塗られている．

K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を求めよ．

入力例 1

4 5
WRWRW
BWRWB
WRWRW
RWBWR

出力例 1

11

入出力例 1 において，古い旗には下図のように色が塗られている．

下図において，X の書かれた 11 個のマスを塗り替える．

これにより下図のようなロシアの旗にすることができる．

11 個未満のマスを塗り替えることではロシアの旗にすることはできないため，11 を出力する．

入力例 2

6 14
WWWWWWWWWWWWWW
WBBBWWRRWWBBBW
WWBWWRRRRWWBWW
BWBWWRRRRWWBWW
WBBWWWRRWWBBBW
WWWWWWWWWWWWWW

出力例 2

44

入出力例 2 においては，古い旗には下図のように色が塗られている．

問題

JOI 国には東西に走る 1 本の十分に長い道路がある．JOI 国の王宮が道路沿いにあり，JOI 国における道路沿いの位置は整数 A で表される．A = 0 のときは王宮の位置を表す．A > 0 のときは，王宮から東へ A メートル進んだ位置を表す．A < 0 のときは，王宮から西へ -A メートル進んだ位置を表す．

JOI 国の道路沿いには N 軒の家があり，家には西から順に 1 から N までの番号が付けられている．JOI 国には N 人の国民がいて，国民には 1 から N までの番号が付けられている．家 i には国民 i が住んでいる．家 i の位置は 0 でない偶数 A_i で表される．A_1, \ldots, A_N は全て異なる．

JOI 国では，近年国民の運動不足が問題になっている．国民の健康が気になった JOI 国の王様は，国民全員に散歩をする命令を出した．王様が命令を出すと，全ての国民は一斉に東向きまたは西向きに歩き始める．それぞれの国民がどちらの向きに歩き始めるかは，国民ごとに決まっている．全ての国民は，歩くときは 1 秒あたり 1 メートルの速度で歩く．

JOI 国の国民は皆おしゃべりが大好きである．散歩の途中にほかの国民に出会うと，その場所で立ち止まって世間話を始めてしまう．すでに立ち止まっている国民に出会った場合も同様である．一度立ち止まった国民は，再び歩き出すことはない．

JOI 国には Q 人の重要人物がいる．JOI 国の王様は，命令が出されてから T 秒後の，Q 人の重要人物の位置を把握しておきたい．命令が出されてから T 秒後の，Q 人の重要人物の位置を求めるプログラムを作成せよ．

入力例 1

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5

出力例 1

-6
-6
15

入力例 2

7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
4
5
7

出力例 2

-82
-16
-13
-13
0

問題

JOI 君が住んでいる島がゾンビに侵略されてしまった．JOI 君は島で一番安全な避難場所として設定されているシェルターに逃げ込むことにした．

JOI 君が住んでいる島は町 1 から町 N までの N 個の町からなり，町と町とは道路で結ばれている．島には M 本の道路があり，すべての道路は異なる 2 つの町を結んでいる．JOI 君は道路を双方向に自由に移動できるが，道路以外を通って町から別の町に行くことはできない．

いくつかの町はゾンビに支配されており，訪れることが出来ない．ゾンビに支配されている町から S 本以下の道路を使って到達できる町を危険な町という．それ以外の町を危険でない町という．

JOI 君の家は町 1 にあり，避難先のシェルターは町 N にある．町 1，町 N はゾンビに支配されていない．島の道路は移動するのに時間がかかるので，JOI 君は町を移動するたびに，移動先の町で一晩宿泊しなければならない．JOI 君は，危険でない町で宿泊する場合は宿泊費が P 円の安い宿に泊まるが，危険な町で宿泊する場合はセキュリティのサービスが優良な宿泊費が Q 円の高級宿に泊まる．JOI 君はできるだけ宿泊費が安くなるように移動して，町 N まで避難したい．町 1 や町 N では宿泊する必要はない．

JOI 君が 町 1 から町 N まで移動するときに必要な宿泊費の合計の最小値を求めよ．

入力例 1

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

出力例 1

11000

入出力例 1 は，以下の図に対応している．円は町を，線は道路を表す．

この場合，町 3，町 4，町 6，町 8，町 12 が危険な町である．

以下のような順番で町を移動すると，宿泊費の合計を最小にできる．

• 町 1 から町 2 に行く．町 2 で宿泊費が 1\,000 円の安い宿に宿泊する．
• 町 2 から町 5 に行く．町 5 で宿泊費が 1\,000 円の安い宿に宿泊する．
• 町 5 から町 9 に行く．町 9 で宿泊費が 1\,000 円の安い宿に宿泊する．
• 町 9 から町 10 に行く．町 10 で宿泊費が 1\,000 円の安い宿に宿泊する．
• 町 10 から町 11 に行く．町 11 で宿泊費が 1\,000 円の安い宿に宿泊する．
• 町 11 から町 12 に行く．町 12 で宿泊費が 6\,000 円の高級宿に宿泊する．
• 町 12 から町 13 に行く．町 13 では宿泊しない．

JOI 君がこのような経路で移動したとき，宿泊費の合計は 11\,000 円になるので，11\,000 を出力する．

入力例 2

21 26 2 2
1000 2000
5
16
1 2
1 3
1 10
2 5
3 4
4 6
5 8
6 7
7 9
8 10
9 10
9 11
11 13
12 13
12 15
13 14
13 16
14 17
15 16
15 18
16 17
16 19
17 20
18 19
19 20
19 21

出力例 2

15000

問題

JOI 君の住む IOI 市は，南北方向に H 区画，東西方向に W 区画の長方形の形をしており，H \times W 個の区画に区切られている．北から i 番目，西から j 番目の区画を (i, j) と表す．現在，IOI 市で開催されている国際的なプログラミングコンテストを記念して，大規模なお祭りが開催されている．いくつかの区画には屋台が出ており，それぞれ違う種類のお菓子を販売している． 区画 (1, 1)，区画 (H, W) およびそれらに東西南北に隣接する区画には屋台はない．

JOI 君は区画 (1, 1) から区画 (H, W) に移動する．移動時間を短くするため，JOI 君は東あるいは南のみに移動を行う．JOI 君はお菓子が好きなので，区画に入るごとに順に次の行動をとる．

• 現在の区画にまだ買っていないお菓子を販売している屋台が出ている場合，その屋台でお菓子を購入する．
• 現在の区画の東西南北に隣接する区画にまだ買っていないお菓子を販売している屋台が出ている場合，それらの屋台のうち 1 つを除く全ての屋台から販売員を呼んで，お菓子を購入する．

JOI 君は同じ種類のお菓子を複数回購入することはない．

IOI 市の大きさ，屋台の位置と，それぞれの屋台のお菓子の値段が与えられたとき，JOI 君が区画 (1, 1) から区画 (H, W) に移動する間に購入するお菓子の総額の最小値を求めよ．

入力例 1

5 5
..483
.59.9
3.866
79...
4.8..

出力例 1

20

入出力例 1 においては，区画 (1, 1)，区画 (2, 1)，区画 (3, 1)，区画 (3, 2)，区画 (4, 2)，区画 (4, 3)，区画 (4, 4)，区画 (4, 5)，区画 (5, 5) の順番に移動して，区画 (3, 1)，区画 (3, 3)，区画 (4, 2) の屋台で販売しているお菓子を購入すると，購入するお菓子の総額が最小となる．

入力例 2

12 10
..498522.4
.633527629
54.4621596
634.213458
1924518685
7739539767
276155.3.6
87716372.2
.858877595
7998739511
3438.5852.
568.9319..

出力例 2

63