{"raw_statement":[{"iden":"statement","content":"Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Укконен (и его друзья) для самых маленьких».\n\nК сожалению, Рудольфу не всегда удавалось приобрести все выходящие книги, поэтому сейчас у него скопилось N неполных книжных коллекций. Рудольф хочет оставить только полные коллекции, поэтому он решил, что с каждой из имеющихся коллекций он поступит одним из двух способов — либо докупит недостающие книги, либо продаст имеющиеся.\n\nВ интернет-магазинах Рудольфу удалось найти все интересующие книги, и теперь он знает, что i-ю из его коллекций можно сделать полной за Ai рублей либо продать за Bi рублей.\n\nУ Рудольфа есть M рублей, которые он может потратить на приобретение книг; кроме того, приобретать книги можно и на деньги, вырученные от продажи книг. Рудольф хочет собрать как можно больше полных коллекций. Помогите ему определить, какое максимальное количество коллекций он сможет получить, если будет покупать и продавать книги оптимальным образом.\n\nПервая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа.\n\nСледующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг.\n\nСледующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа.\n\nВыведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф.\n\n"},{"iden":"входные данные","content":"Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа.Следующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг.Следующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа."},{"iden":"выходные данные","content":"Выведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф."},{"iden":"примеры","content":"Входные данные3600 600200 800300 550415Выходные данные2Входные данные6130 160110 170190 120180 130180 180100 170170Выходные данные3"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of incomplete book collections.  \nFor each collection $ i \\in \\{1, \\dots, N\\} $:  \n- $ A_i \\in \\mathbb{Z}_{\\geq 0} $: cost to complete the collection.  \n- $ B_i \\in \\mathbb{Z}_{\\geq 0} $: revenue from selling the collection.  \n\nLet $ M \\in \\mathbb{Z}_{\\geq 0} $ be the initial amount of money.  \n\n**Decision Variables**  \nFor each collection $ i $, define:  \n- $ x_i \\in \\{0, 1, 2\\} $:  \n  - $ x_i = 0 $: sell the collection (gains $ B_i $),  \n  - $ x_i = 1 $: do nothing,  \n  - $ x_i = 2 $: complete the collection (spends $ A_i $).  \n\n**Constraints**  \n1. $ \\sum_{i=1}^N \\left( x_i = 2 \\right) \\cdot A_i - \\sum_{i=1}^N \\left( x_i = 0 \\right) \\cdot B_i \\leq M $  \n2. $ x_i \\in \\{0, 1, 2\\} $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nMaximize:  \n$$\n\\sum_{i=1}^N \\mathbb{I}(x_i = 2)\n$$","simple_statement":"Rudolf has N incomplete book collections. For each collection i, he can either:\n\n- Spend Ai rubles to complete it, or  \n- Sell it for Bi rubles.\n\nHe starts with M rubles and can use money from selling collections to buy others.\n\nGoal: Maximize the number of complete collections.","has_page_source":false}