A. Скачивание оперативной памяти
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

А вы знали, что вы можете скачать дополнительную оперативную память? Есть магазин с $$$n$$$ разными программами, каждая из которых увеличивает вашу оперативную память (ОЗУ). $$$i$$$-й программе, увеличивающей ОЗУ, требуется $$$a_i$$$ гигабайт памяти, чтобы выполниться (память занимается временно, как только программа завершит работу, память снова освободится), и после ее использования она увеличит вашу ОЗУ на $$$b_i$$$ гигабайт (навсегда). Каждая программа может быть использована не более одного раза. Изначально у вашего компьютера $$$k$$$ гигабайт оперативной памяти.

Заметьте, что вы не можете использовать программу, увеличивающую ОЗУ, если ей требуется больше гигабайт оперативной памяти, чем есть у вашего компьютера в момент запуска. Вы можете использовать программы, увеличивающие ОЗУ, в любом порядке.

Для вас ОЗУ — самая важная вещь на свете, и поэтому вам очень интересно узнать, какое максимальное количество гигабайт ОЗУ вы сможете получить?

Входные данные

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество тестов. Описание тестовых примеров следует ниже.

Первая строка каждого тестового примера содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 1000$$$). Затем следует две строки, каждая из которых содержит $$$n$$$ целых чисел, описывающих массивы $$$a$$$ и $$$b$$$ ($$$1 \le a_i, b_i \le 1000$$$).

Выходные данные

Для каждого тестового примера выведите одну строку, содержащую максимально-возможный объем оперативной памяти.

Пример
Входные данные
4
3 10
20 30 10
9 100 10
5 1
1 1 5 1 1
1 1 1 1 1
5 1
2 2 2 2 2
100 100 100 100 100
5 8
128 64 32 16 8
128 64 32 16 8
Выходные данные
29
6
1
256
Примечание

В первом наборе входных данных изначально у вас достаточно оперативной памяти только для запуска третьей программы, и после ее использования ваша оперативная память увеличится до $$$20$$$ гигабайт, что позволит вам использовать первую программу и увеличить объем оперативной памяти до $$$29$$$ гигабайт. Единственная оставшаяся программа требует $$$30$$$ гигабайт ОЗУ и ее нельзя будет использовать.

Во втором наборе входных данных вы можете использовать все программы кроме третьей, которые требуют всего $$$1$$$ гигабайт для запуска, чтобы увеличить объем ОЗУ до $$$5$$$ гигабайт, а затем использовать третью программу, чтобы увеличить объем ОЗУ до $$$6$$$ гигабайт.

В третьем наборе входных данных каждая программа требует более $$$1$$$-го гигабайта ОЗУ для запуска, поэтому объем имеющейся у вас оперативной памяти останется равным $$$1$$$ гигабайту.