貨物列車 (Freight Train)

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 2 - N .

1 ≦ A i ≦ 1 000 000 ( 2 ≦ i ≦ N ).

入力される値はすべて整数である.

( 6 点) W = 1 , A i = 1 ( 2 ≦ i ≦ N ).

( 9 点) A i = 1 ( 2 ≦ i ≦ N ).

( 24 点) W = 1 .

( 13 点) N ≦ 15 .

( 24 点) N ≦ 50 .

( 24 点) 追加の制約はない.

入力は以下の形式で与えられる.

N W D

A 2 A 3 ... A N

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

생성자가 기록되지 않았습니다.

출처 JOI 2023 Preliminary 2