Проходит очередной финал Start[c]up, поэтому необходимо заказать пиццу для финалистов, участвующих в соревновании в офисе компании. Существует всего два типа пиццы (конечно нет, но в этой задаче будем считать, что да), все пиццы содержат одинаковое число S кусочков.
Известно, что i-й участниц съест si кусочков пиццы, и получит ai единиц счастья от съедания каждого кусочка пиццы первого типа, и bi единиц счастья от съедания каждого кусочка пиццы второго типа. Мы можем заказать любое число пицц первого и второго типов, но мы хотим заказать минимальное число пицц, необходимое для того, чтобы все участники могли съесть необходимое каждому число кусочков. Учитывая это ограничение, какое максимальное суммарное число единиц счастья могут получить участники?
Выходные данные
Выведите максимальное суммарное счастье, которое могут получить участники.
Примечание
В первом примере нужно купить лишь одну пиццу. Если это будет пицца первого типа, то суммарное счастье будет равно 3·5 + 4·6 + 5·9 = 84, а если купить пиццу второго типа — то суммарное счастье будет равно 3·7 + 4·7 + 5·5 = 74.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 12
3 5 7
4 6 7
5 9 5
|
84
|
|
2
|
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6
|
314
|