TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬出生後四十二天大的故事。

某些人可能會聽過或看過,如果都沒有印象的話可以複習一下在題目第一段的敘述,殿壬在一個月大的時候已經會數數了。
那出生第四十二天要做甚麼呢,距離大約還有一年半才可以養拉不拉多和貓咪,所以那時無聊的殿壬只能複習數數和複習比大小。

殿壬是藉由計算一串數字當中有幾個「洞」來練習數數。在練習十二天後他開始觀察洞,洞跟環很像,環跟數字很像。所以同時為了繼續練習數數,殿壬養成了一種新的興趣,就是在環上依序寫下很多數字。

接下來為了準備在 $11$ 個月之內學會寫程式,殿壬想到了一個程式題目:

殿壬會在地上寫了 $N$ 個數字並圍成了一個環,依照順序分別是 $a_0, a_1, ..., a_{N - 1}$, 其中 $a_i$ 與$a_{(i + 1) \% N}$相鄰。
程式現在會把這 $N$ 個數字分成 $K$ 組,每一組都由環上相鄰的數字組成,為了公平起見,殿壬要求每一組都不能超過 $L$ 個數字。
分好後殿壬會把每一組的所有數字加起來,並對這個分配方式評定快樂度,快樂度為 $K$ 組總和裡面的最小值。

殿壬想要快樂度最大,這樣可能會比較快樂,可是殿壬那時候還不會寫程式,所以你來寫?

Input Format

輸入第一行有三個正整數 $N, K, L$ ,分別代表 $N$ 個數字、分成 $K$ 組、每組不超過 $L$ 個數字。
輸入第二行有 $N$ 個整數依序代表 $a_0, a_1, ..., a_{N - 1}$ 。

  • $1 \leq N \leq 1000$
  • $1 \leq K \leq N$
  • $1 \leq L \leq N$
  • $N \leq K \times L$
  • 對環裡面每個數字 $\lvert a_i \rvert \leq 10^ {12}$

Output Format

請輸出一行共一個數字,代表所有可能的合法分組方案裡面快樂度的最大值。

Sample Input

5 2 3
-7 42 10 -8 -5

Sample Output

2

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 262144 262144
1 2500 262144 262144
2 2500 262144 262144
3 2500 262144 262144
4 2500 262144 262144
5 2500 262144 262144
6 2500 262144 262144
7 2500 262144 262144
8 2500 262144 262144
9 2500 262144 262144
10 2500 262144 262144
11 2500 262144 262144
12 2500 262144 262144
13 2500 262144 262144
14 2500 262144 262144
15 2500 262144 262144
16 2500 262144 262144
17 2500 262144 262144
18 2500 262144 262144
19 2500 262144 262144
20 2500 262144 262144
21 2500 262144 262144
22 2500 262144 262144
23 2500 262144 262144
24 2500 262144 262144
25 2500 262144 262144
26 2500 262144 262144
27 2500 262144 262144
28 2500 262144 262144
29 2500 262144 262144