Problem1392--#6035. 「雅礼集训 2017 Day4」洗衣服

1392: #6035. 「雅礼集训 2017 Day4」洗衣服

Time Limit: 3 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

你现在要洗 l l l 件衣服。你有 n n n 台洗衣机和 m m m 台烘干机。由于你的机器非常的小,因此你每次只能洗涤(烘干)一件衣服。

i i i 台洗衣机洗一件衣服需要 wi w_i wi 分钟,第 i i i 台烘干机烘干一件衣服需要 di d_i di 分钟。

请问把所有衣服洗干净并烘干,最少需要多少时间?假设衣服在机器间转移不需要时间,并且洗完的衣服可以过一会再烘干。

Input

输入文件的第一行三个整数 l l ln n nm m m
第二行 n n n 个整数 wi w_i wi
第三行 m m m 个整数 di d_i di

Output

一行一个整数,表示所需的最少时间。

Sample Input Copy

1 1 1
1200
34

Sample Output Copy

1234

HINT

对于 10% 10\% 10% 的数据,l=1 l = 1 l=1
对于另外 20% 20\% 20% 的数据,l,n,m≤10 l, n, m \leq 10 l,n,m10
对于另外 30% 30\% 30% 的数据,l≤1000,n,m≤100 l \leq 1000, n, m \leq 100 l1000,n,m100
对于 100% 100\% 100% 的数据,l≤106,n,m≤105 l \leq 10 ^ 6, n, m \leq 10 ^ 5 l106,n,m105

Source/Category