Quy hoạch động 2

Hãy xem xét một hệ thống tiền bao gồm \(n\) đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tính số lượng các cách khác nhau mà bạn có thể tạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn.

Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(8\) cách:

• \(2+2+5\)
• \(2+5+2\)
• \(5+2+2\)
• \(3+3+3\)
• \(2+2+2+3\)
• \(2+2+3+2\)
• \(2+3+2+2\)
• \(3+2+2+2\)

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn.
• Dòng thứ hai có \(n\) số nguyên phân biệt biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.

Output

• In một số nguyên: số lượng cách, chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq x \leq 10^6\)
• \(1 \leq c_i \leq 10^6\)

Example

3 9
2 3 5

8

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

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

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^9)\)

• \(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^3)\)

Output

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

Example

3 8
3 30
4 50
5 60

90

Cho \(n\) món đồ được đánh chỉ số từ \(1\) đến \(n\), món đồ thứ \(i\) có trọng lượng \(w_{i}\) và giá trị \(v_{i}\). Hãy chọn một số món đồ sao cho tổng trọng lượng không vượt quá \(m\) và tổng giá trị là lớn nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 10^{5})\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(w_{i}\) và \(v_{i}\) \((1 \leq w_{i}, v_{i} \leq 10)\).

Output

• Một dòng duy nhất chứa một số nguyên là tổng giá trị lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \leq 10^{3}\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 15
6 5
5 6
6 4
6 6
3 5
7 2

17