安东正在玩一款非常有趣的电脑游戏,但现在他卡在其中一个关卡上。为了进入下一关,他必须准备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。