Bài tập

Một cửa hàng có \(n\) món đồ, món thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Bạn được chọn một số món (mỗi món tối đa một lần) sao cho tổng khối lượng nằm trong đoạn \([U, V]\), nghĩa là không nhỏ hơn \(U\) và không lớn hơn \(V\). Hãy tìm tổng giá trị lớn nhất có thể. Nếu không có cách chọn nào hợp lệ thì in ra \(0\).

Input

• Dòng đầu: ba số nguyên \(n\), \(U\), \(V\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(w_i\) và \(v_i\).

Output

• In ra tổng giá trị lớn nhất có thể (hoặc \(0\) nếu không có cách chọn hợp lệ).

Constraints

• \(1 \le n \le 40\)
• \(1 \le U \le V \le 4 \times 10^{10}\)
• \(1 \le w_i, v_i \le 10^9\)

Sample Input

4 6 10
4 5
3 4
6 7
5 6

Sample Output

12

Một cửa hàng đang giảm giá có \(n\) món đồ, món thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Bạn có một chiếc túi chứa được tổng khối lượng tối đa \(M\). Hãy chọn một số món (mỗi món dùng nhiều nhất một lần) sao cho tổng khối lượng không vượt quá \(M\) và tổng giá trị là lớn nhất có thể.

Input

• Dòng đầu: hai số nguyên \(n\), \(M\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(w_i\) và \(v_i\).

Output

• In ra tổng giá trị lớn nhất có thể đạt được.

Constraints

• \(1 \le n \le 40\)
• \(1 \le M \le 4 \times 10^{10}\)
• \(1 \le w_i, v_i \le 10^9\)

Sample Input

4 10
4 5
3 4
6 7
5 6

Sample Output

12

Explanation

Chọn món 1 và món 3 (khối lượng \(4+6=10\), giá trị \(5+7=12\)). Chọn món 2 và món 4 chỉ được giá trị 10, nên đáp án là 12.

Có \(N\) quả trứng chạy trên băng chuyền theo thứ tự, quả thứ \(i\) có thể tích \(a_i\). Ở cuối băng chuyền có \(M\) thùng đặt liên tiếp, mỗi thùng có sức chứa \(K\) như nhau. Các quả trứng lần lượt được cho vào thùng đầu tiên cho đến khi quả kế tiếp không còn vừa (tổng thể tích sẽ vượt \(K\)), khi đó chuyển sang thùng tiếp theo và cứ thế tiếp tục.

Hãy tìm \(K\) nhỏ nhất (số nguyên không âm) sao cho \(M\) thùng chứa hết tất cả trứng.

Input

• Dòng đầu gồm hai số nguyên \(N, M\).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra giá trị \(K\) nhỏ nhất.

Constraints

• \(1 \le N \le 10^6\)
• \(1 \le M \le 10^9\)
• \(0 \le a_i \le 10^6\)

Sample Input

6 3
3 7 2 5 4 6

Sample Output

10

Explanation

Với \(K = 10\): thùng 1 chứa \(3+7\), thùng 2 chứa \(2+5\), thùng 3 chứa \(4+6\). Với \(K = 9\) thì phải dùng ít nhất \(4\) thùng.

Trước mặt bạn Hải có \(n\) lọ thuốc màu xếp thành một hàng, mỗi lọ có một màu là số nguyên từ \(0\) đến \(99\). Hải muốn trộn tất cả chúng thành một lọ duy nhất. Mỗi lần, Hải chọn hai lọ đứng cạnh nhau, đổ vào nhau để được một lọ mới nằm đúng vị trí hai lọ cũ.

• Trộn hai lọ màu \(a\) và \(b\) cho ra lọ màu \((a + b) \bmod 100\).
• Mỗi lần trộn như vậy sinh ra lượng khói bằng \(a \cdot b\).

Ví dụ, với ba lọ màu \(5, 8, 7\): trộn lọ 2 và 3 được \(5, 15\) (khói \(56\)), rồi trộn nốt được một lọ màu \(20\) (khói \(75\)).

Hãy tìm cách trộn sao cho tổng lượng khói sinh ra là nhỏ nhất và in ra lượng khói đó.

Input

Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm hai dòng:

• Dòng đầu chứa số nguyên \(n\) là số lọ.
• Dòng thứ hai chứa \(n\) số nguyên là màu ban đầu của các lọ, theo thứ tự từ trái sang phải.

Dữ liệu kết thúc ở cuối tệp. Số bộ test không quá \(20\).

Output

Với mỗi bộ test in ra một dòng là lượng khói nhỏ nhất.

Constraints

• \(1 \le n \le 100\)
• Mỗi màu là một số nguyên từ \(0\) đến \(99\).

Sample Input

3
25 40 70
1
50
4
12 34 56 78

Sample Output

3050
0
3140

Explanation

Với bộ test đầu: nếu trộn \(25\) với \(40\) trước (khói \(1000\), được màu \(65\)) rồi trộn với \(70\) (khói \(4550\)) thì tổng là \(5550\). Cách tốt hơn là trộn \(40\) với \(70\) trước (khói \(2800\), được màu \(10\)) rồi trộn \(25\) với \(10\) (khói \(250\)), tổng \(3050\). Bộ test thứ hai chỉ có một lọ nên không sinh khói.