Bài tập

Trên băng chuyền của một quán lẩu có \(N\) món ăn, món thứ \(i\) được Quang chấm độ ngon \(A_i\) và được Quân chấm độ ngon \(B_i\).

Hai bạn muốn chọn ra đúng \(K\) món sao cho trung bình cộng của (tổng độ ngon theo Quang) và (tổng độ ngon theo Quân) là lớn nhất. Nói cách khác, cần tối đa hoá

với \(S\) là tập \(K\) món được chọn.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(A_1, \dots, A_N\).
• Dòng thứ ba chứa \(B_1, \dots, B_N\).

Output

In ra giá trị lớn nhất tìm được, là số thực với đúng một chữ số thập phân.

Constraints

• \(1 \le K \le N \le 10^5\).
• \(1 \le A_i, B_i \le 10^9\).

Sample Input 1

5 2
8 3 5 9 1
2 6 4 1 7

Sample Output 1

10.0

Sample Input 2

4 3
1 2 3 4
1 1 1 2

Sample Output 2

6.5

Explanation

Ở ví dụ 1, tổng \(A_i+B_i\) của các món là \(10, 9, 9, 10, 8\); chọn hai món có tổng \(10\) được \((10+10)/2 = 10.0\). Ở ví dụ 2, các tổng là \(2,3,4,6\); chọn ba món lớn nhất được \(13/2 = 6.5\).

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