Maximum Distinct Colors in a Necklace

You are given n different colors of beads and a desired necklace length k. For each color i, there are a_i beads available and you are allowed to use at most b_i beads of that color. The number of beads you can actually use from color i is \(\min(a_i, b_i)\). Your task is to determine the maximum number of distinct colors that can be used to form a necklace such that the total number of beads does not exceed k. This problem requires you to choose the colors in a greedy fashion, sorting them by \(\min(a_i, b_i)\) and then adding beads from each color until you cannot add a full set from any additional color without exceeding k.

inputFormat

The input is read from standard input and has the following format:

• The first line contains two integers n and k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁹), where n is the number of bead colors and k is the desired necklace length.
• Each of the next n lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10⁹), representing the number of beads available and the maximum number of beads that can be used of the i-th color, respectively.

outputFormat

Output a single integer to standard output, which is the maximum number of distinct colors that can be used to form a necklace without exceeding a total of k beads.

5 8
3 2
4 3
5 5
2 2
6 1

4