← 返回题目列表

Codeforces · 734/C

C. 安东和制作魔药

中文机器翻译题面 查看原题

安东正在玩一款非常有趣的电脑游戏,但现在他卡在其中一个关卡上。为了进入下一关,他必须准备n种药剂。

安东有一个特殊的水壶,可以在x秒内准备一剂药水。此外,他还知道两种可以加快魔药制备过程的咒语。

1. 此类法术会加快一剂药水的准备时间。有 m 个此类法术,其中第 i 个法术消耗 bi 点法力值,并将每种药水的准备时间从 x 改为 ai。
2. 这种类型的法术会立即准备一些药剂。有 k 个这样的法术,其中第 i 个需要消耗 di 法力点并立即产生 ci 药水。

安东可以使用不超过一个第一类型法术和不超过一个第二类型法术,并且消耗的法力值总数不应超过s。考虑到所有法术都是在安东开始准备药剂之前立即使用的。

安东想要尽快进入下一关,因此他感兴趣的是他需要花费最少的时间来准备至少 n 种药剂。

输入

输入的第一行包含三个整数 n、m、k (1 ≤ n ≤ 2·109, 1 ≤ m, k ≤ 2·105) – Anton 必须制作的药剂数量、第一类型咒语数量和第二类型咒语数量。

输入的第二行包含两个整数 x 和 s (2 ≤ x ≤ 2·109, 1 ≤ s ≤ 2·109)——准备一剂药水所需的初始秒数以及安东可以使用的法力点数量。

第三行包含 m 个整数 ai (1 ≤ ai < x) - 如果使用第一种类型的第 i 个咒语,准备一瓶药水所需的秒数。

第四行包含 m 个整数 bi (1 ≤ bi ≤ 2·109) — 使用第一种类型的第 i 个法术的法力点数。

第五行有 k 个整数 ci (1 ≤ ci ≤ n) - 如果使用第二种类型的第 i 个咒语,将立即创建的药水数量。保证 ci 不会递减,即如果 i < j,则 ci ≤ cj。

第六行包含 k 个整数 di (1 ≤ di ≤ 2·109) — 使用第二种类型的第 i 个法术所需的法力点数量。保证 di 不会减少,即如果 i < j,则 di ≤ dj。

输出

打印一个整数——准备 n 瓶药水所需的最短时间。

示例

输入 #1

20 3 2
10 99
2 4 3
20 10 40
4 15
10 80

输出 #1

20

输入 #2

20 3 2
10 99
2 4 3
200 100 400
4 15
100 800

输出 #2

200

注意

在第一个示例中,最佳答案是使用第一种类型的第二个法术,消耗 10 点法力值。这样,每份药水的准备时间就变成了4秒。另外,安东应该使用第二类法术立即准备15瓶药剂,花费80点法力值。总共使用的法力值是10+80=90,准备时间是4·5=20秒(瞬间准备了15份药剂,剩下的5份每份需要4秒)。

在第二个样本中,安东无法使用任何法术,因此他只准备了 20 种药剂,每种药剂花费 10 秒,答案为 20·10 = 200。