eolymp
bolt
Try our new interface for solving problems
Problems

Robots (RU)

Robots (RU)

Time limit 1 second
Memory limit 64 MiB

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа А, а вторую – роботы типа В. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

Составьте программу, которая по заданному набору роботов обоих типов определяет, за какое минимальное время они смогут обработать определенное количество деталей.

Input data

В первой строке натуральное число N, 1N100000 – количество деталей, которое необходимо обработать.

Во второй строке натуральное число Na, 1Na1000 – количество роботов, выполняющих первую операцию.

В третьей строке через пробел Na натуральных чисел A_i, 1A_i100 – время, которое тратит i-ый робот типа А на выполнение операции.

В четвертой строке натуральное число Nb, 1Nb1000 – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел Nb натуральных чисел B_i, 1B_i100 – время, которое тратит i-ый робот типа В на выполнение операции.

Output data

В первой строке одно целое число – минимальное время, за которое все N деталей будут обработаны сначала роботом типа A, а потом роботом типа В. Временем передачи детали от робота типа А роботу типа В пренебречь.

Examples

Input example #1
6
3
1 3 2
2
2 3
Output example #1
9