Bài tập

Chủ trại có \(N\) con trâu, con thứ \(i\) mỗi ngày cày đúng \(a_i\) đơn vị diện tích. Một khách muốn thuê một số con trâu để cày một mảnh ruộng có diện tích đúng \(S\) (không thừa, không thiếu). Hỏi có thể chọn một tập con các con trâu sao cho tổng diện tích cày được bằng đúng \(S\) hay không?

Input

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

Output

• In YES nếu chọn được, ngược lại in NO.

Constraints

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

Sample Input

6 11
4 7 2 9 5 3

Sample Output

YES

Explanation

Chọn con thứ nhất và con thứ hai: \(4 + 7 = 11\).

Một chiếc mũ sinh nhật có dạng hình nón với chiều cao \(h\) và bán kính đáy \(R\) (đều là số nguyên dương). Hãy tính thể tích của hình nón đó, biết công thức \(V = \dfrac{1}{3}\pi R^2 h\) (lấy \(\pi = 3.14159265358979\ldots\)).

Input

• Một dòng gồm hai số nguyên \(h\) và \(R\), cách nhau một dấu cách.

Output

• In ra thể tích hình nón, làm tròn đúng \(8\) chữ số thập phân.

Constraints

• \(1 \le h, R \le 1000\)

Sample Input

3 5

Sample Output

78.53981634

Explanation

\(V = \dfrac{1}{3}\pi \cdot 5^2 \cdot 3 = 25\pi \approx 78.53981634\).

Kho vật tư có \(n\) thanh thép, thanh thứ \(i\) dài \(a_i\) đơn vị. Cần cưa các thanh này để có ít nhất \(K\) đoạn thép cùng chiều dài nguyên. Không bắt buộc dùng hết mọi thanh; mỗi thanh có thể còn phần dư sau khi cưa.

Tìm chiều dài lớn nhất của các đoạn thép mà vẫn đủ \(K\) đoạn.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(K\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, \dots, a_n\).

Output

In ra một số nguyên là chiều dài lớn nhất. Nếu không thể cưa được \(K\) đoạn có chiều dài nguyên dương nào thì in ra \(0\).

Constraints

• \(1 \le n \le 5 \cdot 10^5\), \(1 \le K \le 10^9\).
• \(1 \le a_i \le 10^9\).

Subtask: \(60\%\) số test có \(n \le 3000\); \(40\%\) số test còn lại có \(n \le 500\,000\).

Sample Input

5 10
30 21 8 14 5

Sample Output

7

Explanation

Với chiều dài \(7\): \(4 + 3 + 1 + 2 + 0 = 10\) đoạn. Với chiều dài \(8\) chỉ được \(3+2+1+1+0 = 7\) đoạn.

Cho \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) và một số nguyên dương \(K\). Hãy chọn một tập con của các phần tử (mỗi phần tử dùng nhiều nhất một lần) có tổng chia hết cho \(K\) và có số phần tử nhiều nhất. Nếu không tồn tại tập con khác rỗng nào thỏa mãn thì in \(0\).

Input

• Dòng đầu: hai số nguyên \(n\) và \(K\).
• Dòng thứ hai: \(n\) số nguyên \(A_1, \dots, A_n\).

Output

• In ra số phần tử lớn nhất của một tập con có tổng chia hết cho \(K\).

Constraints

• \(1 \le K \le 4 \times 10^{10}\), \(1 \le A_i \le 10^9\)
• Subtask 1: \(1 \le n \le 20\)
• Subtask 2: \(21 \le n \le 40\)

Sample Input

6 5
3 7 2 8 4 1

Sample Output

6

Explanation

Tổng cả sáu số là \(25\), chia hết cho \(5\).