{"problem":{"name":"B. Рудольф и книжные коллекции","description":{"content":"Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Ук","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10176B"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nПервая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа.Следующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг.Следующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа.\n\n## Выходные Данные\n\nВыведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф.\n\n## Примеры\n\nВходные данные3600 600200 800300 550415Выходные данные2Входные данные6130 160110 170190 120180 130180 180100 170170Выходные данные3\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10176B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}