Knapsack 1

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^5)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^9)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90

Bạn đang ở trong một hiệu sách bán \(n\) cuốn sách khác nhau. Bạn biết giá và số trang của mỗi cuốn sách.

Bạn quyết định tổng số tiền mua sách của bạn tối đa là \(x\). Tổng số trang tối đa bạn có thể mua là bao nhiêu? Bạn chỉ có thể mua mỗi cuốn sách nhiều nhất một lần.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng sách và tổng số tiền tối đa
• Dòng tiếp theo chứa \(n\) số nguyên \(h_1,h_2,\ldots,h_n\): giá cả của mỗi cuốn sách
• Dòng cuối cùng chứa \(n\) số nguyên \(s_1,s_2,\ldots,s_n\): số trang của mỗi cuốn sách

Constraints

• \(1 \leq n \leq 1000\)
• \(1 \leq x \leq 10^5\)
• \(1 \leq h_i,s_i \leq 1000\)

Output

• In một số nguyên duy nhất: tổng số trang tối đa

Example

4 10
4 8 5 3
5 12 8 1

13

Bạn có \(n\) đồng xu với các giá trị nhất định. Nhiệm vụ của bạn là tìm tất cả các khoản tiền bạn có thể tạo bằng những đồng xu này.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng đồng xu
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của các đồng xu

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq x_i \leq 1000\)

Output

• Dòng đầu tiên in ra một số nguyên \(k\): số lượng khoản tiền khác nhau có thể tạo
• Dòng tiếp theo in ra \(k\) số nguyên: các khoản tiền có thể tạo được, theo thứ tự tăng dần

Example

4
4 2 5 2

9
2 4 5 6 7 8 9 11 13

Hãy đếm số cách mà các số \(1, 2,\ldots,n\) có thể được chia thành hai tập hợp có tổng bằng nhau.

Ví dụ, với \(n = 7\), có \(4\) cách chia:

• \(\{1,3,4,6\}\) và \(\{2,5,7\}\)
• \(\{1,2,5,6\}\) và \(\{3,4,7\}\)
• \(\{1,2,4,7\}\) và \(\{3,5,6\}\)
• \(\{1,6,7\}\) và \(\{2,3,4,5\}\)

Input

• Gồm một dòng duy nhất chứa số nguyên \(n\) \((1 \leq n \leq 500)\).

Output

• In đáp án - số cách thoả mãn chia lấy dư cho \(10^9 + 7\).

Example

7

4