第22回日本情報オリンピック　二次予選

2022年12月13日
情報オリンピック日本委員会

問題文

IOI 鉄道は 1 本の鉄道路線を運営している．IOI 鉄道線には一直線上に並んだ N 個の駅があり，順に 1 から N までの番号が付けられている．各 i (1 ≦ i ≦ N - 1) に対して，駅 i と駅 i + 1 の間は線路で結ばれており，その長さは 1 である．

IOI 鉄道は貨物を取り扱っている．駅 2, 3, …, N には貨物が 1 つずつ置かれており，駅 i (2 ≦ i ≦ N) に置かれている貨物の価値は A_i である．

IOI 鉄道は貨物列車を 1 編成所有している．この列車は最初駅 1 におり，IOI 鉄道線上を双方向に走行できる．それぞれの駅では，その駅に置いてある貨物を列車に積むことや，列車に積まれている貨物を下ろし，その駅に置いておくことができる．

この貨物列車を用いて 駅 2, 3, …, N に置かれている貨物を駅 1 に輸送したい．ただし，この列車には貨物を W 個以下しか載せることができない．すなわち，どの時点においても列車に貨物が W + 1 個以上載っていることは許されない．また，この列車は燃料の都合上，最大でも総距離 D しか走行することができない．そのため，すべての貨物を駅 1 に輸送することはできないかもしれない．

IOI 鉄道の社長である JOI くんは，この条件のもと適切に貨物列車を走行させることで，最終的に駅 1 に置かれている貨物の価値の合計をなるべく大きくしたい．

貨物列車の情報と各駅に置かれている貨物の情報が与えられたとき，最終的に駅 1 に置かれている貨物の価値の合計として達成可能な最大値を求めるプログラムを作成せよ．

制約

• 2 ≦ N ≦ 450．
• 1 ≦ W ≦ N - 1．
• 2 ≦ D ≦ N² - N．
• 1 ≦ A_i ≦ 1 000 000 (2 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (6 点) W = 1，A_i = 1 (2 ≦ i ≦ N)．
2. (9 点) A_i = 1 (2 ≦ i ≦ N)．
3. (24 点) W = 1．
4. (13 点) N ≦ 15．
5. (24 点) N ≦ 50．
6. (24 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N W D
A₂ A₃ … A_N

出力

最終的に駅 1 に置かれている貨物の価値の合計として達成可能な最大値を 1 行で出力せよ．

入出力例

入力例 1
4 1 10
1 1 1

出力例 1
2

例えば，以下のように貨物列車を走行させると最終的に駅 1 に置かれている貨物の価値の合計を 2 にすることができる．

最初，貨物列車は駅 1 にいる．

1. 貨物列車を駅 2 に走行させる．
2. 駅 2 に置かれている価値 1 の貨物を貨物列車に積む．
3. 貨物列車を駅 1 に走行させる．
4. 貨物列車に積まれている価値 1 の貨物を駅 1 に置く．
5. 貨物列車を駅 4 に走行させる．
6. 駅 4 に置かれている価値 1 の貨物を貨物列車に積む．
7. 貨物列車を駅 1 に走行させる．
8. 貨物列車に積まれている価値 1 の貨物を駅 1 に置く．

列車の走行した総距離は 8 であり，列車が総距離 10 以下しか走行できないという条件を満たしている．

このとき，最終的に駅 1 に置かれている貨物の価値の合計は 2 である．最終的に駅 1 に置かれている貨物の価値の合計を 3 以上にすることはできないため，2 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2
7 3 16
1 1 1 1 1 1

出力例 2
5

例えば，以下のように貨物列車を走行させると最終的に駅 1 に置かれている貨物の価値の合計を 5 にすることができる．

最初，貨物列車は駅 1 にいる．

1. 貨物列車を駅 5 に走行させる．
2. 駅 5 に置かれている価値 1 の貨物を貨物列車に積む．
3. 貨物列車を駅 6 に走行させる．
4. 駅 6 に置かれている価値 1 の貨物を貨物列車に積む．
5. 貨物列車を駅 1 に走行させる．
6. 貨物列車に積まれている 2 つの価値 1 の貨物をすべて駅 1 に置く．
7. 貨物列車を駅 2 に走行させる．
8. 駅 2 に置かれている価値 1 の貨物を貨物列車に積む．
9. 貨物列車を駅 3 に走行させる．
10. 駅 3 に置かれている価値 1 の貨物を貨物列車に積む．
11. 貨物列車を駅 4 に走行させる．
12. 駅 4 に置かれている価値 1 の貨物を貨物列車に積む．
13. 貨物列車を駅 1 に走行させる．
14. 貨物列車に積まれている 3 つの価値 1 の貨物をすべて駅 1 に置く．

列車の走行した総距離は 16 であり，列車が総距離 16 以下しか走行できないという条件を満たしている．

このとき，最終的に駅 1 に置かれている貨物の価値の合計は 5 である．最終的に駅 1 に置かれている貨物の価値の合計を 6 以上にすることはできないため，5 を出力する．

この入力例は小課題 2, 4, 5, 6 の制約を満たす．

入力例 3
5 2 12
40 30 20 10

出力例 3
100

例えば，以下のように貨物列車を走行させると最終的に駅 1 に置かれている貨物の価値の合計を 100 にすることができる．

最初，貨物列車は駅 1 にいる．

1. 貨物列車を駅 5 に走行させる．
2. 駅 5 に置かれている価値 10 の貨物を貨物列車に積む．
3. 貨物列車を駅 4 に走行される．
4. 駅 4 に置かれている価値 20 の貨物を貨物列車に積む．
5. 貨物列車を駅 2 に走行させる．
6. 貨物列車に積まれている価値 10 の貨物と価値 20 の貨物を駅 2 に置く．
7. 駅 2 に置かれている価値 40 の貨物を貨物列車に積む．
8. 貨物列車を駅 3 に走行させる．
9. 駅 3 に置かれている価値 30 の貨物を貨物列車に積む．
10. 貨物列車を駅 1 に走行させる．
11. 貨物列車に積まれている価値 30 の貨物と価値 40 の貨物を駅 1 に置く．
12. 貨物列車を駅 2 に走行させる．
13. 駅 2 に置かれている価値 10 の貨物と価値 20 の貨物を貨物列車に積む．
14. 貨物列車を駅 1 に走行させる．
15. 貨物列車に積まれている価値 10 の貨物と価値 20 の貨物を駅 1 に置く．

列車の走行した総距離は 12 であり，列車が総距離 12 以下しか走行できないという条件を満たしている．

このとき，最終的に駅 1 に置かれている貨物の価値の合計は 100 である．最終的に駅 1 に置かれている貨物の価値の合計を 101 以上にすることはできないため，100 を出力する．

この入力例は小課題 4, 5, 6 の制約を満たす．

入力例 4
5 1 11
2 7 1 8

出力例 4
10

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 5
9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

出力例 5
2214425

この入力例は小課題 4, 5, 6 の制約を満たす．