Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Укконен (и его друзья) для самых маленьких».
К сожалению, Рудольфу не всегда удавалось приобрести все выходящие книги, поэтому сейчас у него скопилось N неполных книжных коллекций. Рудольф хочет оставить только полные коллекции, поэтому он решил, что с каждой из имеющихся коллекций он поступит одним из двух способов — либо докупит недостающие книги, либо продаст имеющиеся.
В интернет-магазинах Рудольфу удалось найти все интересующие книги, и теперь он знает, что i-ю из его коллекций можно сделать полной за Ai рублей либо продать за Bi рублей.
У Рудольфа есть M рублей, которые он может потратить на приобретение книг; кроме того, приобретать книги можно и на деньги, вырученные от продажи книг. Рудольф хочет собрать как можно больше полных коллекций. Помогите ему определить, какое максимальное количество коллекций он сможет получить, если будет покупать и продавать книги оптимальным образом.
Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа.
Следующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг.
Следующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа.
Выведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф.
3
600 600
200 800
300 550
415
2
6
130 160
110 170
190 120
180 130
180 180
100 170
170
3
| 2018 III Интеллектуальная олимпиада ПФО |
|---|
| Закончено |
