А вы знали, что вы можете скачать дополнительную оперативную память? Есть магазин с \(n\) разными программами, каждая из которых увеличивает вашу оперативную память (ОЗУ). \(i\)-й программе, увеличивающей ОЗУ, требуется \(a_i\) гигабайт памяти, чтобы выполниться (память занимается временно, как только программа завершит работу, память снова освободится), и после ее использования она увеличит вашу ОЗУ на \(b_i\) гигабайт (навсегда). Каждая программа может быть использована не более одного раза. Изначально у вашего компьютера \(k\) гигабайт оперативной памяти.
Заметьте, что вы не можете использовать программу, увеличивающую ОЗУ, если ей требуется больше гигабайт оперативной памяти, чем есть у вашего компьютера в момент запуска. Вы можете использовать программы, увеличивающие ОЗУ, в любом порядке.
Для вас ОЗУ — самая важная вещь на свете, и поэтому вам очень интересно узнать, какое максимальное количество гигабайт ОЗУ вы сможете получить?
Выходные данные
Для каждого тестового примера выведите одну строку, содержащую максимально-возможный объем оперативной памяти.
Примечание
В первом наборе входных данных изначально у вас достаточно оперативной памяти только для запуска третьей программы, и после ее использования ваша оперативная память увеличится до \(20\) гигабайт, что позволит вам использовать первую программу и увеличить объем оперативной памяти до \(29\) гигабайт. Единственная оставшаяся программа требует \(30\) гигабайт ОЗУ и ее нельзя будет использовать.
Во втором наборе входных данных вы можете использовать все программы кроме третьей, которые требуют всего \(1\) гигабайт для запуска, чтобы увеличить объем ОЗУ до \(5\) гигабайт, а затем использовать третью программу, чтобы увеличить объем ОЗУ до \(6\) гигабайт.
В третьем наборе входных данных каждая программа требует более \(1\)-го гигабайта ОЗУ для запуска, поэтому объем имеющейся у вас оперативной памяти останется равным \(1\) гигабайту.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|