Codeforces Round 932 (Div. 2) |
---|
Закончено |
В новом мессенджере для учащихся Центра Помощи Магистрам, Кефтемерум, планируется обновление, в котором разработчики хотят оптимизировать набор сообщений, показываемых пользователю. Всего есть $$$n$$$ сообщений, каждое сообщение характеризуется двумя целыми числами $$$a_i$$$ и $$$b_i$$$. Время, потраченное на прочтение набора сообщений с номерами $$$p_1, p_2, \ldots, p_k$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны) рассчитывается по формуле:
$$$$$$\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|$$$$$$
Обратите внимание, что время прочтения набора сообщений, состоящего из одного сообщения с номером $$$p_1$$$, равно $$$a_{p_1}$$$. Также время прочтения пустого набора сообщений считается равным $$$0$$$.
Пользователь может сам определить время $$$l$$$, которое он готов провести в мессенджере. Мессенджер же должен сообщить пользователю максимально возможный размер набора сообщений, время прочтения которого не превышает $$$l$$$. Обратите внимание, что максимальный размер набора сообщений может быть равен $$$0$$$.
Разработчики популярного мессенджера не справились внедрить данную функцию, поэтому попросили вас решить эту задачу.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$l$$$ ($$$1 \leq n \leq 2000$$$, $$$1 \leq l \leq 10^9$$$) — количество сообщений и время, которое пользователь готов провести в мессенджере.
$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — характеристики $$$i$$$-го сообщения.
Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^6$$$.
Для каждого набора входных данных выведите одно целое число — максимально возможный размер набора сообщений, время прочтения которого не превышает $$$l$$$.
55 84 31 52 44 32 31 64 103 124 82 12 125 2624 78 2830 223 817 175 1415 31000000000 998244353179 239228 1337993 1007
3 1 2 1 0
В первом наборе входных данных, можно взять набор из трёх сообщений с номерами $$$p_1 = 3$$$, $$$p_2 = 2$$$ и $$$p_3 = 5$$$. Время, затрачиваемое на прочтение данного набора, равно $$$a_3 + a_2 + a_5 + |b_3 - b_2| + |b_2 - b_5| = 2 + 1 + 2 + |4 - 5| + |5 - 3| = 8$$$.
Во втором наборе входных данных, можно взять набор из одного сообщения со номером $$$p_1 = 1$$$. Время, затрачиваемое на прочтение данного набора, равно $$$a_1 = 4$$$.
В пятом наборе входных данных можно показать, что не существует такого непустого набора сообщений, затрачиваемое время на прочтение которого не превышает $$$l$$$.
Название |
---|