An được mời tham gia trò chơi 'Siêu thị may mắn' do đài truyền hình ZTV tổ chức.

Siêu thị được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến ~n~ và mặt hàng thứ ~i~ được niêm yết giá là ~c_{i}~ đồng, ~i = 1, 2, \dots, n~.

Theo thể lệ của trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là ~s~ đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thị với điều kiện mặt hàng thứ ~i~ chỉ được mua với số lượng nhiều nhất là ~m_{i}~ , ~i = 1, 2, \dots, n~.

An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.

Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị ~n~, ~s~, ~c_{i}~ và ~m_{i}~ ~(1 \leq n \leq 500;\; 1 \leq s \leq 10^{5}; \; 1 \leq c_{i} \leq 10^{4};\; 1 \leq m_{i} \leq 100)~ với ~i = 1, 2, \dots, n~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~s~ và ~n~.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên dương ~c_{i}~ và ~m_{i}~ với ~i = 1, 2, \dots, n~.

Output

Gồm 1 dòng duy nhất ghi số nguyên ~d~ là tổng số cách mua hàng tìm được.

Sample Input

12 3
4 1
6 2
2 1

Sample Output

2