Description

There are $n$ different types of tumors by the roadside. For type $i$, there are $k_i$ items available, and each item occupies $d_i$ units of space. Salamander’s bag has a maximum total volume capacity of $m$.

Salamander is very greedy, but he does not require taking as many items as possible or achieving the largest possible total volume. He only requires that the bag can no longer fit any tumor of any remaining type.

Formally, choose integers $x_i$ with $0 \le x_i \le k_i$ for each $i$, such that $\sum_i x_i d_i \le m$, and if $x_i < k_i$ then the remaining capacity $m - \sum_i x_i d_i < d_i$ for every such $i$.

Salamander wants to know how many different packing schemes there are. Two schemes are different if and only if the set of types taken is different, or there exists at least one type for which the taken quantity is different. Since the number of schemes can be large, output the answer modulo $19260817$.

Input Format

The first line contains two positive integers $n$ and $m$, the number of tumor types and the bag’s capacity.

Each of the next $n$ lines contains two positive integers $k_i$ and $d_i$, describing one type of tumor.

Output Format

Output a single line with the number of different schemes, modulo $19260817$.

2 5
2 3
3 1

2

Hint

Sample explanation:

The two schemes are as follows:

1. Take 1 item of type 1 and 2 items of type 2.
2. Take 3 items of type 2.

$~$ $~$

Constraints

• For 10% of the testdata, $1 \le n, k_i, d_i \le 10$, $1 \le m \le 100$;
• For 30% of the testdata, $1 \le n, k_i, d_i \le 50$, $1 \le m \le 5000$;
• For another 20% of the testdata, $k_i = 1$;
• For 100% of the testdata, $1 \le n, k_i, d_i \le 500$, $1 \le m \le 10^5$.

Translated by ChatGPT 5