Bài tập

Cho một dãy gồm \(n\) số nguyên không âm \(p_1, p_2, \dots, p_n\). Hãy chọn ra đúng \(k\) đoạn con liên tiếp, đôi một không giao nhau, mỗi đoạn có độ dài đúng \(m\), tức là chọn các cặp \([L_1, R_1], [L_2, R_2], \dots, [L_k, R_k]\) thoả

Trong tất cả các cách chọn, hãy tìm cách làm cho tổng các phần tử nằm trong \(k\) đoạn được chọn là lớn nhất và in ra tổng đó.

Input

• Dòng đầu chứa ba số nguyên \(n\), \(m\), \(k\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\).

Output

In ra một số nguyên là tổng lớn nhất có thể đạt được.

Constraints

• \(1 \le n \le 5000\), \(1 \le m \cdot k \le n\) (luôn chọn được \(k\) đoạn)
• \(0 \le p_i \le 10^9\)

Sample Input 1

7 2 2
5 1 4 3 8 2 6

Sample Output 1

19

Sample Input 2

6 2 3
4 4 1 9 9 0

Sample Output 2

27

Sample Input 3

5 3 1
0 6 7 2 1

Sample Output 3

15

Explanation

Ở ví dụ 1 chọn đoạn \([4,5]\) (tổng \(3+8=11\)) và đoạn \([6,7]\) (tổng \(2+6=8\)), được \(19\). Ở ví dụ 2 phải dùng toàn bộ dãy vì \(m \cdot k = n\). Ở ví dụ 3 chỉ chọn một đoạn dài 3, tốt nhất là \(6+7+2=15\).

Chủ trại có \(N\) con trâu, con thứ \(i\) cày được đúng \(a_i\) đơn vị diện tích. Cần chọn một tập con các con trâu sao cho tổng diện tích bằng đúng \(S\).

Nếu không chọn được, in NO. Nếu chọn được, in YES cùng một phương án cụ thể. Vì có thể có nhiều phương án, hãy in phương án mà dãy chỉ số các con trâu được chọn (xếp tăng dần) nhỏ nhất theo thứ tự từ điển (so sánh lần lượt từ phần tử đầu tiên).

Input

• Dòng 1: hai số nguyên \(N\) và \(S\).
• Dòng 2: \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• Nếu không có phương án, in NO.
• Ngược lại in ba dòng: dòng 1 là YES; dòng 2 là số con trâu được chọn; dòng 3 là các chỉ số của chúng theo thứ tự tăng dần, cách nhau bởi dấu cách.

Constraints

• \(1 \le N \le 32\)
• \(1 \le S \le 3.2 \times 10^{10}\)
• \(1 \le a_i \le 10^9\)

Sample Input

5 9
4 2 6 3 1

Sample Output

YES
3
1 2 4

Explanation

Các tập có tổng 9 gồm chỉ số \(\{1,2,4\}\) (4+2+3), \(\{3,4\}\) (6+3), \(\{2,3,5\}\) (2+6+1), ... Dãy chỉ số 1 2 4 nhỏ nhất theo thứ tự từ điển.

Trong một lô giày chuẩn bị xuất xưởng, mỗi cỡ giày xuất hiện đúng hai chiếc (một đôi), trừ duy nhất một cỡ chỉ có một chiếc lẻ. Cho danh sách cỡ của tất cả các chiếc giày trong lô, hãy in ra cỡ của chiếc giày lẻ đó.

Input

• Dòng đầu chứa số nguyên lẻ \(n\) là tổng số chiếc giày.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\), trong đó \(a_i\) là cỡ của chiếc thứ \(i\).

Dữ liệu đảm bảo: có đúng một cỡ xuất hiện một lần, mọi cỡ còn lại xuất hiện đúng hai lần.

Output

• In ra một số nguyên duy nhất: cỡ của chiếc giày lẻ.

Constraints

• \(1 \le n \le 3 \cdot 10^6\), \(n\) lẻ
• \(1 \le a_i \le 10^{18}\)

Sample Input 1

7
40 38 41 38 39 40 41

Sample Output 1

39

Chủ trại có \(N\) con trâu, con thứ \(i\) nặng \(w_i\). Ông chọn ra một số con trong đàn (có thể không phải tất cả) rồi chia số con được chọn thành đúng hai nhóm không giao nhau sao cho tổng cân nặng hai nhóm bằng nhau. Hãy tìm tổng cân nặng lớn nhất của mỗi nhóm có thể đạt được. Nếu không thể chia được với cả hai nhóm khác rỗng thì in \(0\).

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(w_1, \dots, w_N\).

Output

• In ra tổng cân nặng lớn nhất của một nhóm.

Constraints

• \(1 \le N \le 22\)
• \(1 \le w_i \le 10^9\)

Sample Input

5
3 3 6 2 4

Sample Output

9

Explanation

Nhóm 1: \(\{3, 6\}\), nhóm 2: \(\{3, 2, 4\}\), mỗi nhóm nặng 9.