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.

Output

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

Constraints

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

Example

Sample input

4 10
4 8 5 3
5 12 8 1

13

Note

Bạn có thể mua các cuốn sách \(1\) và \(3\). Giá của chúng là \(4 + 5 = 9\) và số lượng trang là \(5 + 8 = 13\).

Nhiệm vụ của bạn là đếm số cách tạo ra tổng \(n\) bằng cách gieo xúc xắc một hoặc nhiều lần. Mỗi lần gieo cho ra số từ \(1\) đến \(6\).

VÍ dụ, nếu \(n = 3\), có \(4\) cách:

• \(1 + 1 + 1\)
• \(1 + 2\)
• \(2 + 1\)
• \(3\)

Input

• Dòng đầu vào duy nhất có số nguyên \(n\).

Output

• In số cách chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \leq n \leq 10^6\)

Example

Sample input

3

4

Hãy 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ạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn sao cho số lượng đồng xu là tối thiểu.

Ví dụ: nếu các đồng xu là \(\{1,5,7\}\) và tổng mong muốn là \(11\), một giải pháp tối ưu là \(5 + 5 + 1\), cần \(3\) đồng xu.

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 \(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 đồng xu tối thiểu. Nếu không thể tạo ra tổng mong muốn, hãy in \(−1\).

Constraints

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

Example

Sample input

3 11
1 5 7

Sample output

3

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

Sample input

3 9
2 3 5

Sample output

8

Xét một hệ thống tiền tệ với \(n\) loại đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Hãy tính số cách khác nhau, không kể thứ tự để tạo ra tổng tiền \(x\) từ những đồng này.

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

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

Input

Định dạng đầu vào:

• Dòng đầu tiên chứa 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 chứa \(n\) số nguyên riêng biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.

Output

• In một số nguyên duy nhất: 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

Sample input

3 9  
2 3 5

Sample output

3

Bạn được cho một số nguyên \(n\). Ở mỗi bước, bạn có thể trừ \(n\) đi một lượng bằng một trong các chữ số của nó.

Cần bao nhiêu bước để làm cho \(n\) bằng \(0\)?

Input

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

Output

• In ra một số nguyên duy nhất là số bước tối thiểu cần dùng.

Constraints

• \(1 \leq n \leq 10 ^ 6\)

Example

Sample input

27

Sample output

5

Note

Một giải pháp tối ưu là \(27 \to 20 \to 18 \to 10 \to 9 \to 0\).

Xét một lưới ô vuông kích thước \(n \times n\), trong đó một số ô có thể có bẫy. Ta không được phép đi qua một ô có bẫy.

Hãy tính số lượng đường đi từ góc trên trái đến góc dưới phải của lưới, biết rằng ta chỉ được đi sang phải hoặc đi xuống dưới.

Input

• Dòng đầu tiên chứa một số nguyên \(n\): kích thước của lưới.
• \(n\) dòng sau, mỗi dòng chứa \(n\) kí tự mô tả lưới: . biểu thị một ô trống và * biểu thị một cái bẫy.

Output

• In ra một số nguyên duy nhất là số lượng đường đi chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

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

Example

Sample input

4  
....  
.*..  
...*  
*...

Sample output

3