問題文

JOI 君は鉛筆を N 本買うために近くの文房具店に行くことにした．

文房具店では鉛筆が一定の本数ずつのセットで売られている．セット X は A 本で B 円，セット Y は C 本で D 円である．

JOI 君はセット X かセット Y の一方を選び，選んだセットをいくつか購入する．両方のセットを購入することはできない．N 本以上の鉛筆を得るために必要な金額の最小値を求めよ．

制約

• 1 ≦ N ≦ 1000
• 1 ≦ A ≦ 1000
• 1 ≦ B ≦ 1000
• 1 ≦ C ≦ 1000
• 1 ≦ D ≦ 1000

入力例 1

10 3 100 5 180

出力例 1

360

JOI 君は10本の鉛筆を入手したい．セット X は3本で100円，セット Y は5本で180円である．この時，セット X を選んだ場合は，セットを4つ購入する必要があり400円必要である．セット Y を選んだ場合は，セットを2つ購入する必要があり360円必要である．したがって，必要な金額の最小値は400円と360円の小さい方で360円である．

入力例 2

6 2 200 3 300

出力例 2

600

このとき，セット X を選んだ場合もセット Y を選んだ場合も必要な金額は600円である．必要な金額の最小値は600円である．

問題文

JOI 君はおじさんの家で双六を見つけた．双六は直線状に並んだ N+2 個のマスからなり，1 番目のマスはスタート，N+2 番目のマスはゴールである．その他の各マスには 0 または 1 が書かれていて，各 i (1≦i≦N) について，i+1 番目のマスに書かれた数字は A_i である．

双六では，最初にスタートのマスにコマを置き，サイコロを振って，出た目の数だけコマを進めることを繰り返す．ただし，1 の書かれたマスに止まった場合は，ゲームオーバーである．ゲームオーバーにならずにゴールのマスに止まるか，ゴールのマスを通り過ぎたら，ゲームクリアである．

JOI 君は双六を遊ぶためのサイコロをおもちゃ屋さんに買いに行くことにした．おもちゃ屋さんには N+1 個のサイコロが売っている．j 番目 (1≦j≦N+1) のサイコロは j 個の面を持ち，1,2,...,j が 1 つずつ書かれている．

JOI 君はゲームクリアできるようなサイコロのうち，最も面の数が少ないサイコロを 1 個買うことにした．JOI 君はどのサイコロを買えばよいだろうか．

制約

• 1≦N≦100
• 0≦A_i≦1 (1≦i≦N)

入力例 1

5
0 1 0 0 0

出力例 1

2

双六は 7 マスからなり，3 マス目のみに 1 が書かれている．面の数が 2 個のサイコロを使った場合，例えば出た目が 1,2,1,1,1 となったときにゲームクリアすることができる．これが最小なので 2 を出力する．

入力例 2

5
1 1 1 1 1

出力例 2

6

双六は 7 マスからなり，スタートとゴール以外のマス全てに 1 が書かれている．このとき，面の数が 6 個のサイコロが必要である．これが最小なので 6 を出力する．

入力例 3

7
0 0 1 0 1 1 0

出力例 3

3

問題文

JOI 市は，東西方向にまっすぐに伸びる H 本の道路と，南北方向にまっすぐに伸びる W 本の道路によって，碁盤の目の形に区分けされている．道路と道路の間隔は 1 である．JOI 市では，これら H+W 本の道路から，東西方向に 1 本，南北方向に 1 本，合計 2 本の道路を幹線道路として選ぶことになった．

北から i 本目 (1≦i≦H) の道路と，西から j 本目 (1≦j≦W) の道路の交差点を，交差点 (i,j) とする．交差点 (i,j) と北から m 本目 (1≦m≦H) の道路の距離は |i-m| であり，交差点 (i,j) と西から n 本目 (1≦n≦W) の道路の距離は |j-n| である． また，交差点 (i,j) の近くには A_{i,j} 人の住人が住んでいる．

2 本の幹線道路を選んだときの，JOI 市の全ての住人に対する，最寄りの交差点から近い方の幹線道路への距離の総和の最小値を求めよ．

制約

• 2 ≦ H ≦ 25
• 2 ≦ W ≦ 25
• 0 ≦ A_{i,j} ≦ 100 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

入力例 1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 1

8

例えば，北から 2 本目の道路と西から 1 本目の道路を幹線道路とすればよい．

入力例 2

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5

出力例 2

164

北から 3 本目の道路と西から 2 本目の道路を幹線道路とすればよい．

問題文

水ようかんとは，おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である．いま，JOI 君の手元には，横長の直方体の形をした水ようかんがひとつある．JOI 君は，今日のおやつとしてこの水ようかんを食べる予定である．

この水ようかんには，縦方向の切れ目が全部で N-1 箇所に入っている．水ようかんの長さは L_1 + L_2 + ... + L_N であり，i 番目 (1 ≦ i ≦ N-1) の切れ目は，左から L_1 + L_2 + ... + L_i の位置にある．

この水ようかんは丸ごと食べるには大きすぎるので，JOI 君は，水ようかんに入っている切れ目から 1 箇所以上を選び，選んだ切れ目に沿って水ようかんを切って，複数のピースに切り分けることにした．ただし，ピースの大きさが不揃いでは見栄えが悪いので，長さ最大のピースと最小のピースの長さの差ができるだけ小さくなるように切ることにした．

長さ最大のピースと最小のピースの長さの差の最小値を求めよ．

制約

• 2 ≦ N ≦ 50
• 1 ≦ L_i ≦ 1000 (1 ≦ i ≦ N)

入力例 1

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

出力例 1

2

この例では，4 番目および 7 番目の切れ目に沿って切り分けることで，長さ 17, 19, 18 の 3 つのピースに切り分けることができる． このとき，いちばん長いピースは長さ 19 で，いちばん短いピースは長さ 17 であるので，長さの差は 2 となる． これが最小値なので，2 を出力する．

入力例 2

2
1
10

出力例 2

9

どんなに大きさが不揃いであっても，必ず 1 箇所以上を切る必要がある．

入力例 3

5
5
5
5
5
5

出力例 3

0

この例では水ようかんをちょうど同じ大きさの 5 つのピースに分割できる．

問題文

JOI 王国には広大な森林がある．森林は長方形の形をしており，南北に H マス，東西に W マスのマス目状に分けられている．北から i マス目，西から j マス目(1 ≦ i ≦ H, 1 ≦ j ≦ W)の領域には A_{i,j} 本の木が生えている．ただし，北西の端の領域には木材加工工場があり，木が生えていない．すなわち，A_{1,1}=0 である．

木が生えていない領域には人が立ち入ることが出来る．また人は東西南北に隣接する領域に，その領域に木が生えていなければ，移動することができる．森林の外に出ることはできない．JOI 君は JOI 王国の公共事業として，木を伐採し，北西の端の領域と南東の端の領域を，相互に行き来可能にしたい．

木の伐採は以下のようにして行う．はじめ，JOI 君は木材加工工場のある北西の端の領域にいる．JOI 君は，現在いる領域と東西南北に隣接する木の生えていない領域に 1 分で移動することができる．また，東西南北に隣接する木の生えている領域から，1 分で木を 1 本伐採することができる．ただし，木を 1 本伐採したら，そのたびに北西の端の領域にある木材加工工場まで伐採した木を運ばなければならない．木を運んでいる間も，JOI 君の移動速度は変わらない．木を運んでいる間は，他の木を伐採することはできない．

条件を満たすように木を伐採するのにかかる時間の最小値を求めよ．ただし，伐採にかかる時間とは，最後に伐採した木を，木材加工工場に運ぶまでの時間とする．

制約

• 1 ≦ H ≦ 30
• 1 ≦ W ≦ 30
• (H, W) ≠ (1, 1)
• 0 ≦ A_{i,j} ≦ 10000 (1 ≦ i ≦ H, 1 ≦ j ≦ W)
• A_{1,1}=0

入力

入力は以下の形式で標準入力から与えられる．

H W
A_{1,1} ... A_{1,W}
:
A_{H,1} ... A_{H,W}

小課題 2 [28点]

• A_{i,j} ≦ A_{i,j+1} (1 ≦ i ≦ H, 1 ≦ j ≦ W-1)
• A_{i,j} ≦ A_{i+1,j} (1 ≦ i ≦ H-1, 1 ≦ j ≦ W)

小課題 3 [57点]

• 追加の制限はない．

入力例 1

2 3
0 1 2
3 4 5

出力例 1

32

北から i マス目，西から j マス目の領域を (i, j) で表す．

まず (1, 2) の木を伐採する．これには 1 分かかる．

次に (1, 3) の木をすべて伐採する．1 本伐採するのに，(1,1) から東に 1 マス進み，(1, 3) の木を伐採し，西に 1 マス進んで (1,1) に戻ればいいので，3 分かかる．よってこれには 2 × 3 = 6 分かかる．

次に (2, 3) の木をすべて伐採する．1 本伐採するのに，(1,1) から東に 2 マス進み，(2, 3) の木を伐採し，西に 2 マス進んで (1,1) に戻ればいいので， 5 分かかる．よってこれには 5 × 5 = 25 分かかる．

全部で 1 + 6 + 25 = 32 分かかる．これより少ない時間で，条件を満たすように木を伐採することはできないので，32 を出力する．

入力例 2

2 5
0 5 0 0 0
0 0 0 9 1

出力例 2

13

(2, 5) の木のみを伐採すればよい．

入力例 3

2 5
0 2 0 0 0
0 0 0 9 1

出力例 3

11

まず，(1, 2) の木を伐採して，次に (2, 5) の木を伐採すればよい．

問題文

横一列に並べられた N 枚のカードがある．左から i 枚目(1 ≦ i ≦ N)のカードには，整数 a_i が書かれている．

JOI 君は，これらのカードを用いて次のようなゲームを行う．連続する K 枚以上のカードの列を選び，次の操作を行う．

• 選んだカードを，書かれている整数が小さい順に左から並べる．
• 並べたカードのうち，左から K 番目のカードに書かれた整数を紙に書き出す．
• 選んだカードを，すべて元の位置に戻す．

この操作を，連続する K 枚以上のカードの列すべてに対して行う．すなわち，1 ≦ l ≦ r ≦ N かつ K ≦ r - l + 1 を満たすすべての (l,r) について，a_l, a_{l+1}, ..., a_r のうち K 番目に小さな整数を書き出す．

こうして書き出された整数を，左から小さい順に並べる．並べた整数のうち，左から L 番目のものがこのゲームにおける JOI 君の得点である．JOI 君の得点を求めよ．

制約

• 1 ≦ N ≦ 200000
• 1 ≦ K ≦ N
• 1 ≦ a_i ≦ N
• 1 ≦ L
• JOI 君が書き出す整数は L 個以上である．

入力例 1

4 3 2
4 3 1 2

出力例 1

3

1 ≦ l ≦ r ≦ N (= 4) かつ K (= 3) ≦ r - l + 1 を満たす (l,r) は，(1,3), (1,4), (2,4) の 3 通りある．

これらの (l,r) に対し，a_l, a_{l+1}, ..., a_r で 3 番目に小さな整数は，それぞれ 4, 3, 3 である．

このうち L (= 2) 番目に小さい整数は 3 なので，JOI 君の得点は 3 である．同じ整数が複数あるときも，重複して数えることに注意せよ．

入力例 2

5 3 3
1 5 2 2 4

出力例 2

4

JOI 君が書き出す整数は，

• (l,r) = (1,3) に対し 5
• (l,r) = (1,4) に対し 2
• (l,r) = (1,5) に対し 2
• (l,r) = (2,4) に対し 5
• (l,r) = (2,5) に対し 4
• (l,r) = (3,5) に対し 4

である．このうち L (= 3) 番目に小さい整数は 4 である．

入力例 3

6 2 9
1 5 3 4 2 4

出力例 3

4

入力例 4

6 2 8
1 5 3 4 2 4

出力例 4

3