Bài 4

Để động viên Nam chuẩn bị cho kỳ thi học sinh giỏi sắp tới, mẹ cho Nam $M$ đồng ($1 \le M \le 10^3$) mua bút để ôn tập. Khi đến nhà sách, Nam thấy có $N$ ($1 \le N \le 100$) loại bút mà mình muốn mua. Loại bút thứ $i$ có giá là $a_i$ đồng và nhà sách có số lượng là $b_i$ cây ($i = 1..n$, $1 \le a_i, b_i \le 10^3$).

Với số tiền mẹ đã cho, Nam muốn mua được càng nhiều bút càng tốt mà không cần phải có nhiều loại bút khác nhau. Bạn hãy giúp Nam tính toán xem có thể mua tối đa bao nhiêu cây bút.

• Số nguyên $N$ là số loại bút $N$ muốn mua, số nguyên $M$ là số tiền mẹ Nam cho.
• Dòng thứ $i$ trong $N$ dòng sau chứa hai số nguyên $a_i$ và $b_i$ số nguyên ($1 \le a_i, b_i \le 10^3$)

Số lượng bút tối đa mà Nam có thể mua được.

• $1 \le M \le 10^3$
• $1 \le N \le 100$
• $1 \le a_i, b_i \le 10^3$