Bài tập

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\).

Cho số nguyên dương \(n\). Hãy liệt kê tất cả các xâu nhị phân (chỉ gồm 0 và 1) có độ dài đúng \(n\), theo thứ tự từ điển tăng dần.

Input

• Một số nguyên dương \(n\).

Output

• Mỗi dòng một xâu nhị phân, theo thứ tự từ điển tăng dần (\(2^n\) dòng).

Constraints

• \(1 \le n \le 16\)

Sample Input

3

Sample Output

000
001
010
011
100
101
110
111