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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

ii 台洗衣机洗一件衣服需要 wiw_i 分钟,第 ii 台烘干机烘干一件衣服需要 did_i 分钟。

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

输入格式

输入文件的第一行三个整数 llnnmm
第二行 nn 个整数 wiw_i
第三行 mm 个整数 did_i

输出格式

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

样例

样例输入 1

1 1 1
1200
34

样例输出 1

1234

样例输入 2

2 3 2
100 10 1
10 10

样例输出 2

12

数据范围与提示

对于 10%10\% 的数据,l=1l = 1
对于另外 20%20\% 的数据,l,n,m10l, n, m \leq 10
对于另外 30%30\% 的数据,l1000,n,m100l \leq 1000, n, m \leq 100
对于 100%100\% 的数据,l106,n,m105l \leq 10 ^ 6, n, m \leq 10 ^ 5