Minimum Charging Days for Robot Q

Robot Q has been added to the team, but unlike humans, he needs to be powered up by inputting energy. The restaurant provides a menu of N energy units in a fixed order. Each unit provides a certain energy value and requires a given amount of time to be consumed. However, due to technical limitations, Robot Q can only be charged for at most 119 time units per day (if this limit is exceeded, he will crash).

You are allowed to select some of the energy units (in the given order, i.e. you may skip some units) so that the total energy accumulated is at least k. When charging, if adding an energy unit in the current day would cause the day’s total charging time to exceed 119, you must start a new day with that energy unit (its charging time counts on the new day).

Your task is to determine the minimum number of days required to accumulate at least k energy. It is guaranteed that each energy unit requires no more than 119 time units (otherwise that unit cannot be used).

Note: Even if the energy is exactly a multiple of 119 in charging time, the day is counted if any charging occurs during that day.

The formula used for the daily limit is in \( \text{daily time} \le 119 \).

inputFormat

The first line contains two integers \(N\) and \(k\), where \(N\) is the number of available energy units and \(k\) is the minimum required total energy.

Then follow \(N\) lines, each containing two integers separated by a space. The first integer represents the energy value of that unit, and the second integer represents the time required to consume that unit.

You may assume that each unit’s time cost does not exceed 119.

outputFormat

Output a single integer: the minimum number of days needed for Robot Q to accumulate at least \(k\) energy. If it is impossible to obtain \(k\) energy, output -1.

sample

3 5
2 60
3 60
3 10

1