100.0% (1/1)

100.0% (1/1)

# Description

（具體來說，若殿壬選擇的區域為 $[L_1, R_1], \ldots, [L_K, R_K]$ ，則必須滿足 $L_{i + 1} > R_i + 1, \forall 1 \leq i < K$ 且 $L_i \leq R_i, \forall 1 \leq i \leq K$ ，然後殿壬希望 $\displaystyle\sum_{i = 1}^ {K}{(\sum_{j = L_i}^ {R_i}{A_j})}$ 越大越好。）

# Input Format

• $1 \leq N \leq 10^ 4$
• $1 \leq K \leq \min(N, 20)$
• $|A_i| \leq 10^ 6$
• $0 \leq S \leq 10$

# Sample Input

Sample Input 1:
4 2 0
1 2 3 4

Sample Input 2:
4 2 1
1 2 3 4

Sample Input 3:
4 2 0
-1 -2 -3 -4

Sample Input 4:
4 2 1
-1 -2 -3 -4

Sample Input 5:
10 2 1
3 -1 7 -7 2 -6 2 9 -1 -8

Sample Output 1:
8

Sample Output 2:
9

Sample Output 3:
-4

Sample Output 4:
-3

Sample Output 5:
23

# Problem Source

No. Testdata Range Score
1 0~51 1

# Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1
30 1000 262144 262144 1
31 1000 262144 262144 1
32 1000 262144 262144 1
33 1000 262144 262144 1
34 1000 262144 262144 1
35 1000 262144 262144 1
36 1000 262144 262144 1
37 1000 262144 262144 1
38 1000 262144 262144 1
39 1000 262144 262144 1
40 1000 262144 262144 1
41 1000 262144 262144 1
42 1000 262144 262144 1
43 1000 262144 262144 1
44 1000 262144 262144 1
45 1000 262144 262144 1
46 1000 262144 262144 1
47 1000 262144 262144 1
48 1000 262144 262144 1
49 1000 262144 262144 1
50 1000 262144 262144 1
51 1000 262144 262144 1