G. Butterball on a Diet
time limit per test
3 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Butterball is on a diet, so until autumn, his diet will consist only of broccoli, rice, and chicken breast. Butterball can eat any amount of broccoli, but there are restrictions on rice and chicken breast.

Until autumn, Butterball will have exactly $$$n$$$ trips to the store, and for each trip, he knows in advance the amount of dry rice in grams $$$a_i$$$ and the amount of raw chicken breast in grams $$$b_i$$$ that he is going to buy. It is also known that one meal of Butterball will consist of $$$k$$$ grams of rice and chicken breast combined. But Butterball decided not to mix rice and chicken breast from different trips to the store, so a meal will always have one of the following types:

  • $$$x$$$ grams of rice and $$$y$$$ grams of chicken breast which were bought on the same trip to the store, where $$$x + y = k$$$;
  • $$$x_1, x_2, \ldots, x_r$$$ grams of rice ($$$x_1 + x_2 + \ldots + x_r = k$$$), where $$$x_i$$$ is a part of all the rice bought in one of the trips to the store;
  • $$$y_1, y_2, \ldots, y_r$$$ grams of chicken breast ($$$y_1 + y_2 + \ldots + y_r = k$$$), where $$$y_i$$$ is a part of all the chicken breast bought in one of the trips to the store.
All numbers $$$x$$$, $$$y$$$, $$$x_i$$$, and $$$y_i$$$ are integers.

For example, if Butterball has two trips to the store, on the first trip he buys 200 grams of rice and 500 grams of chicken breast, and on the second trip he buys 100 grams of rice and 200 grams of chicken breast, then he will be able to prepare only 2 meals with $$$k = 400$$$. Like this, for instance:

  • first meal: 100 grams of rice and 300 grams of chicken breast from the first trip to the store;
  • second meal: 200 remaining grams of chicken breast from the first trip to the store and 200 grams of chicken breast from the second trip to the store.

Help Butterball determine the maximum number of meals he can prepare for himself until autumn!

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 500$$$): the number of trips to the store and the total weight of food in grams for one meal, respectively.

In the $$$i$$$-th of the following $$$n$$$ lines, two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \leq a_i, b_i \leq 10^9$$$) are given: the amount of grams of rice and chicken breast bought on the $$$i$$$-th trip to the store, respectively.

Output

Output a single integer: the maximum number of meals that Butterball can prepare.

Examples
Input
2 400
200 500
100 200
Output
2
Input
1 350
100 250
Output
1
Input
2 500
100 200
300 100
Output
0
Note

The first example is described above.

In the second example: Butterball can prepare exactly one meal using all the products from the first (and only) trip to the store.

In the third example: Butterball will not be able to prepare any meals because, in both trips to the store, the total weight of rice and chicken breast is less than needed for one meal. Additionally, the total weight of rice from two trips is less than needed for one meal. The same statement is true for chicken breast.