Добро пожаловать на фондовую биржу Codeforces! Сейчас мы довольно ограничены в ресурсах, поэтому в настоящее время разрешаем торговать только акциями компании Codeforces Ltd. Мы надеемся, что вы все равно сможете получать прибыль с рынка!
Утром у вас есть \(n\) возможностей купить акции, \(i\)-я из них позволяет купить столько акций, сколько вы захотите, по цене \(s_i\) бурлей за штуку.
Вечером у вас есть \(m\) возможностей продать акции, \(i\)-я из них позволяет продать столько акций, сколько вы хотите, каждую по цене \(b_i\) бурлей за штуку. Вы не можете продать больше акций, чем у вас есть.
Сейчас утро, у вас есть \(r\) бурлей и нет акций.
Какое максимальное количество бурлей у вас может быть после вечера?
Выходные данные
Выведите одное целое число — максимальное количество бурлей, которое вы можете иметь после вечера.
Примечание
В первом примере, утром у вас есть \(11\) бурлей.
Оптимально купить \(5\) акций по цене \(2\) бурля у второго продавца утром, а затем продать их все третьему продавцу по цене \(5\) бурлей вечером. Таким образом, после вечера у вас будет \(26\) бурлей.
Во втором примере оптимально не покупать и не продавать акции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 11
4 2 5
4 4 5 4
|
26
|
|
2
|
2 2 50
5 7
4 2
|
50
|