Егор славится своим талантом в области спортивного программирования, но мало кто знает, что он также является отличным поваром, который может легко справиться с приготовлением разнообразных блюд.

Его можно назвать CodeChef, учитывая его впечатляющие навыки как в решении проблем FFT, так и в готовке стейков.

Когда организаторы SDU Open нуждались в шеф-поваре, чтобы приготовить стейки для участников конкурса, они знали, что Егор — идеальный человек для этой работы.

В настоящее время в очереди ожидают $$$n$$$ участников, $$$i$$$-й из которых должен съесть хотя бы $$$a_i$$$ стейков, чтобы удовлетворить свой голод и съесть $$$b_i$$$ стейков, чтобы чувствовать себя сытым.

Хотя Егор настроен насытить всех, организаторы хотят сэкомонить на продуктах. Чтобы найти компромисс, Егору было поручено подавать стейки таким образом, чтобы все участники были удовлетворены и в любой момент времени среди обслуженных участников сытых было не больше чем не сытых.

Если известно, что Егор сможет приготовить не более $$$k$$$ стейков, какое максимальное количество участников он может насытить?