Bài tập

Một trang trại có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Chủ trang trại vừa mua một chiếc máy vắt sữa rất kén chọn: mỗi ngày người ta chọn ra một nhóm bò (có thể là bất kỳ tập con nào của đàn, các con bò được phân biệt với nhau kể cả khi cho cùng lượng sữa) và máy chỉ chạy đúng khi tổng lượng sữa của nhóm đúng bằng \(M\).

Hãy cho biết:

1. Có bao nhiêu nhóm bò khác nhau có tổng lượng sữa đúng bằng \(M\).
2. Trong các nhóm như vậy, nhóm nhỏ nhất có bao nhiêu con bò.

Dữ liệu luôn đảm bảo có ít nhất một nhóm thỏa mãn.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(M\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

In ra hai số nguyên cách nhau một dấu cách: số nhóm bò có tổng đúng \(M\) và số con bò ít nhất trong một nhóm như vậy.

Constraints

• \(1 \le n \le 20\)
• \(1 \le M \le 2 \cdot 10^9\)
• \(1 \le a_i \le 10^8\)

Sample Input

6 9
4 5 2 7 3 2

Sample Output

6 2

Explanation

Sáu nhóm có tổng bằng \(9\) là: \(4+5\); \(7+2\) (có hai cách chọn vì có hai con cho \(2\) đơn vị); \(4+3+2\) (hai cách); \(5+2+2\). Nhóm nhỏ nhất gồm \(2\) con.

Một công ty có \(N\) thùng sơn, thùng thứ \(i\) nặng \(a_i\) kg. Công ty chỉ bán nguyên thùng, không bán lẻ. Một khách hàng có thể mua bất kỳ nhóm thùng nào (ít nhất một thùng), tổng khối lượng mua được là tổng khối lượng các thùng đã chọn.

Ví dụ, với các thùng \([3, 2, 4]\): mua \(6\) kg bằng thùng \(2\) và \(3\), mua \(7\) kg bằng thùng \(1\) và \(3\), nhưng không thể mua đúng \(8\) kg.

Hãy đếm xem có bao nhiêu khối lượng dương phân biệt mà khách có thể mua được.

Input

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

Output

In ra một số nguyên là số khối lượng dương khác nhau có thể mua.

Constraints

• \(1 \le N \le 1000\).
• \(0 \le a_i \le 100\).

Sample Input

4
0 2 5 2

Sample Output

5

Explanation

Các khối lượng mua được là \(2, 4, 5, 7, 9\).

Một hồ cá có dạng hình hộp chữ nhật, mặt hồ là hình chữ nhật có hai cạnh \(a\) và \(b\) (mét), độ sâu của hồ là \(c\) (mét). Biết rằng \(1\ m^3\) nước tương đương \(1000\) lít.

Hãy cho biết cần bơm bao nhiêu lít nước để hồ đầy.

Input

• Một dòng gồm ba số nguyên dương \(a, b, c\), cách nhau một dấu cách.

Output

• In ra số lít nước cần bơm.

Constraints

• \(1 \le a, b, c \le 10000\)

Sample Input

3 5 2

Sample Output

30000

Explanation

Thể tích hồ là \(3 \cdot 5 \cdot 2 = 30\ m^3\), tức \(30000\) lít.

Một cửa hàng đánh số các phiếu quà tặng từ \(1\) đến \(n\). Với mỗi phiếu mang số \(U\), bạn được xử lý nó theo cách có lợi nhất trong các cách sau:

• Nếu \(U\) chia hết cho \(a\), phiếu này mang lại \(x\) đồng.
• Nếu \(U\) chia hết cho \(b\), phiếu này mang lại \(y\) đồng.
• Nếu \(U\) chia hết cho cả \(a\) và \(b\), bạn nhận được nhiều hơn trong hai khoản trên, tức \(\max(x, y)\) đồng.
• Nếu \(U\) không chia hết cho \(a\) lẫn \(b\) thì phiếu không mang lại đồng nào.

Hãy tính tổng số tiền lớn nhất có thể thu được sau khi xử lý tất cả các phiếu từ \(1\) đến \(n\).

Input

• Một dòng gồm \(5\) số nguyên dương \(n, a, b, x, y\) cách nhau bởi dấu cách.

Output

• Một số nguyên duy nhất: tổng số tiền lớn nhất thu được.

Constraints

• \(1 \le n, a, b, x, y \le 10^9\)

Sample Input

10 2 3 5 4

Sample Output

33

Explanation

Có \(5\) số chia hết cho \(2\) (2, 4, 6, 8, 10), có \(3\) số chia hết cho \(3\) (3, 6, 9), trong đó số \(6\) chia hết cho cả hai. Tổng: \(4 \cdot 5 + 2 \cdot 4 + \max(5,4) = 20 + 8 + 5 = 33\).