Anton is playing a very interesting computer game, but now he is stuck at one of the levels. To pass to the next level he has to prepare n potions.

Anton has a special kettle, that can prepare one potions in x seconds. Also, he knows spells of two types that can faster the process of preparing potions.  Spells of this type speed up the preparation time of one potion. There are m spells of this type, the i-th of them costs b_{i} manapoints and changes the preparation time of each potion to a_{i} instead of x.  Spells of this type immediately prepare some number of potions. There are k such spells, the i-th of them costs d_{i} manapoints and instantly create c_{i} potions. 

Anton can use no more than one spell of the first type and no more than one spell of the second type, and the total number of manapoints spent should not exceed s. Consider that all spells are used instantly and right before Anton starts to prepare potions.

Anton wants to get to the next level as fast as possible, so he is interested in the minimum number of time he needs to spent in order to prepare at least n potions.


-----Input-----

The first line of the input contains three integers n, m, k (1 ≤ n ≤ 2·10^9, 1 ≤ m, k ≤ 2·10^5) — the number of potions, Anton has to make, the number of spells of the first type and the number of spells of the second type.

The second line of the input contains two integers x and s (2 ≤ x ≤ 2·10^9, 1 ≤ s ≤ 2·10^9) — the initial number of seconds required to prepare one potion and the number of manapoints Anton can use.

The third line contains m integers a_{i} (1 ≤ a_{i} < x) — the number of seconds it will take to prepare one potion if the i-th spell of the first type is used.

The fourth line contains m integers b_{i} (1 ≤ b_{i} ≤ 2·10^9) — the number of manapoints to use the i-th spell of the first type.

There are k integers c_{i} (1 ≤ c_{i} ≤ n) in the fifth line — the number of potions that will be immediately created if the i-th spell of the second type is used. It's guaranteed that c_{i} are not decreasing, i.e. c_{i} ≤ c_{j} if i < j.

The sixth line contains k integers d_{i} (1 ≤ d_{i} ≤ 2·10^9) — the number of manapoints required to use the i-th spell of the second type. It's guaranteed that d_{i} are not decreasing, i.e. d_{i} ≤ d_{j} if i < j.


-----Output-----

Print one integer — the minimum time one has to spent in order to prepare n potions.


-----Examples-----
Input
20 3 2
10 99
2 4 3
20 10 40
4 15
10 80

Output
20

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

Output
200



-----Note-----

In the first sample, the optimum answer is to use the second spell of the first type that costs 10 manapoints. Thus, the preparation time of each potion changes to 4 seconds. Also, Anton should use the second spell of the second type to instantly prepare 15 potions spending 80 manapoints. The total number of manapoints used is 10 + 80 = 90, and the preparation time is 4·5 = 20 seconds (15 potions were prepared instantly, and the remaining 5 will take 4 seconds each).

In the second sample, Anton can't use any of the spells, so he just prepares 20 potions, spending 10 seconds on each of them and the answer is 20·10 = 200.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Amortized analysis

Greedy algorithms


Solutions:
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = [x] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
d = [0] + list(map(int, input().split()))
ab = list(zip(a, b))
ab.sort(key=lambda x: -x[1])
ans = x * n
ind = 0
for (ai, bi) in ab:
	while ind < k + 1 and d[ind] <= s - bi:
		ind += 1
	if ind == 0:
		continue
	tmp = (n - c[ind - 1]) * ai
	ans = min(ans, tmp)
print(ans)


def main():
	read = lambda : map(int, input().split())
	(n, m, k) = read()
	(x, s) = read()
	a = list(read())
	b = list(read())
	c = list(read())
	d = list(read())
	ans = n * x
	if min(b) <= s:
		Min2 = min((a[i] for i in range(m) if b[i] <= s))
		ans = min(ans, n * Min2)
	b = sorted([(b[i], i) for i in range(m)])
	j = 0
	Min = x
	for i in range(k - 1, -1, -1):
		while j < m and b[j][0] + d[i] <= s:
			Min = min(Min, a[b[j][1]])
			j += 1
		if d[i] > s:
			continue
		cur = (n - c[i]) * Min
		ans = min(ans, cur)
	print(ans)
main()


from operator import itemgetter
(n, m, k) = [int(i) for i in input().split()]
(x, s) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]
ab = [[a[i], b[i]] for i in range(m)]
ab = sorted(ab, key=itemgetter(1))
answer = n * x
b_feasible = [i for i in range(m) if ab[i][1] <= s]
if b_feasible:
	answer = min(answer, n * min([ab[i][0] for i in b_feasible]))
d_feasible = [i for i in range(k) if d[i] <= s]
if d_feasible:
	answer = min(answer, x * (n - max([c[i] for i in d_feasible])))
j = k - 1
early_exit = False
for i in range(m):
	while ab[i][1] + d[j] > s:
		if j > 0:
			j -= 1
		else:
			early_exit = True
			break
	if ab[i][1] + d[j] <= s:
		answer = min(answer, (n - c[j]) * ab[i][0])
	if early_exit:
		break
print(answer)


from sys import stdin
from bisect import bisect_right

def main():
	(n, m, k) = stdin_get_ints_from_line()
	(x, s) = stdin_get_ints_from_line()
	a = stdin_get_ints_list_from_line()
	b = stdin_get_ints_list_from_line()
	c = stdin_get_ints_list_from_line()
	d = stdin_get_ints_list_from_line()
	result = n * x
	key = bisect_right(d, s)
	if key != 0:
		spell2_only_result = (n - c[key - 1]) * x
		if spell2_only_result < result:
			result = spell2_only_result
	for (key, val) in enumerate(b):
		if val <= s:
			if a[key] < x:
				cost_left = s - val
				amount_second = 0
				key2 = bisect_right(d, cost_left)
				if key2 != 0:
					amount_second = c[key2 - 1]
				r = (n - amount_second) * a[key]
				if r < result:
					result = r
				if result <= 0:
					break
	print(result) if result > 0 else print(0)

def stdin_get_ints_from_line():
	return (int(x) for x in stdin.readline().strip().split(' '))

def stdin_get_ints_list_from_line():
	return list((int(x) for x in stdin.readline().strip().split(' ')))

def stdin_get_string_from_line():
	return stdin.readline().strip()
main()


(n, m, k) = [int(i) for i in input().split()]
(x, s) = [int(i) for i in input().split()]
a_t = [int(i) for i in input().split()]
a_m = [int(i) for i in input().split()]
b_p = [int(i) for i in input().split()]
b_m = [int(i) for i in input().split()]
min_time = n * x
a_t.append(x)
a_m.append(0)
for i in range(m + 1):
	re_mana = s - a_m[i]
	if re_mana < 0:
		continue
	inf = -1
	sup = k
	while inf < sup - 1:
		mid = (inf + sup) // 2
		if b_m[mid] <= re_mana:
			inf = mid
		else:
			sup = mid
	if inf <= -1:
		min_time = min(min_time, n * a_t[i])
	else:
		min_time = min(min_time, max(0, n - b_p[inf]) * a_t[i])
print(min_time)


import bisect
(n, m, k) = map(int, input().split(' '))
(x, s) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))
d = list(map(int, input().split(' ')))
a.append(x)
b.append(0)
ans = n * x
for i in range(m + 1):
	if b[i] <= s:
		j = bisect.bisect_right(d, s - b[i])
		if j > 0:
			j -= 1
			ans = min(ans, (n - c[j]) * a[i])
		else:
			ans = min(ans, n * a[i])
print(ans)


import math
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
a.insert(0, x)
b.insert(0, 0)
c.insert(0, 0)
d.insert(0, 0)
ans = 1 << 100
for it in range(m + 1):
	mana = s - b[it]
	if mana < 0:
		continue
	(lo, hi) = (0, k)
	while lo != hi:
		mid = math.ceil((lo + hi) / 2)
		if d[mid] <= mana:
			lo = mid
		else:
			hi = mid - 1
	ans = min(ans, (n - c[lo]) * a[it])
print(ans)


(n, m, k) = (int(x) for x in input().split())
(orig, s) = (int(x) for x in input().split())
time1 = [orig] + [int(x) for x in input().split()]
cost1 = [0] + [int(x) for x in input().split()]
make2 = [0] + [int(x) for x in input().split()]
cost2 = [0] + [int(x) for x in input().split()]
ordcost1 = [(x, i) for (i, x) in enumerate(cost1)]
ordcost1.sort()
count = k
best = orig * n
for i in range(m + 1):
	(cost, ind) = ordcost1[i]
	while count > -1 and cost2[count] + cost > s:
		count -= 1
	if count > -1 and time1[ind] * (n - make2[count]) < best:
		best = time1[ind] * (n - make2[count])
print(best)


class First:

	def __init__(self, seconds, cost):
		self.seconds = seconds
		self.cost = cost

class Second:

	def __init__(self, numCreated, cost):
		self.numCreated = numCreated
		self.cost = cost

def solve():
	(potionCount, firstCount, secondCount) = map(int, input().split())
	(secondsOne, manaPoints) = map(int, input().split())
	first = list()
	(a, b) = (list(map(int, input().split())), list(map(int, input().split())))
	for i in range(firstCount):
		first.append(First(a[i], b[i]))
	first.append(First(secondsOne, 0))
	second = [Second(0, 0)]
	(a, b) = (list(map(int, input().split())), list(map(int, input().split())))
	for i in range(secondCount):
		second.append(Second(a[i], b[i]))
	res = int(1e+20)
	for f in first:
		low = 0
		high = len(second) - 1
		while low < high:
			mid = (low + high + 1) // 2
			if f.cost + second[mid].cost > manaPoints:
				high = mid - 1
			else:
				low = mid
		if f.cost + second[low].cost <= manaPoints:
			moar = max(0, potionCount - second[low].numCreated)
			time = moar * f.seconds
			res = min(res, time)
	print(res)
solve()


import sys
import bisect
while True:
	try:
		(n, m, k) = [int(i) for i in input().split()]
		(x, s) = [int(i) for i in input().split()]
		ans = x * n
		a = [int(i) for i in input().split()]
		b = [int(i) for i in input().split()]
		c = [int(i) for i in input().split()]
		d = [int(i) for i in input().split()]
		a.append(x)
		b.append(0)
		for i in range(m + 1):
			if b[i] > s:
				continue
			if s - b[i] < d[0]:
				ans = min(ans, a[i] * n)
				continue
			t = bisect.bisect_right(d, s - b[i]) - 1
			ans = min(ans, (n - c[t]) * a[i])
		print(ans)
	except EOFError:
		break


def binary_search(arr, n, k):
	(l, r) = (0, n - 1)
	while l <= r:
		mid = l + r >> 1
		if arr[mid] <= k:
			l = mid + 1
		else:
			r = mid - 1
	return l

def main():
	(n, m, k) = map(int, input().split())
	(x, s) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	res = n * x
	for i in range(m):
		idx = binary_search(d, k, s - b[i]) - 1
		if idx >= 0:
			res = min(res, (n - c[idx]) * a[i])
	idx = binary_search(d, k, s) - 1
	if idx >= 0:
		res = min(res, (n - c[idx]) * x)
	for i in range(m):
		if b[i] <= s:
			res = min(res, a[i] * n)
	print(res)
main()


(n, m, k) = list(map(int, input().split()))
(x, s) = list(map(int, input().split()))
a_time = list(map(int, input().split()))
a_cost = list(map(int, input().split()))
b_num = list(map(int, input().split()))
b_cost = list(map(int, input().split()))

def binary_search(manapoints):
	nonlocal k, b_cost
	l = 0
	r = k - 1
	pos = -1
	while l <= r:
		mid = int((l + r) / 2)
		if b_cost[mid] <= manapoints:
			l = mid + 1
			pos = mid
		else:
			r = mid - 1
	return pos
res = n * x
pos = binary_search(s)
if pos >= 0:
	res = min(res, (n - b_num[pos]) * x)
for i in range(m):
	if a_cost[i] > s:
		continue
	rest = s - a_cost[i]
	pos = binary_search(rest)
	if pos >= 0:
		res = min(res, (n - b_num[pos]) * a_time[i])
	else:
		res = min(res, n * a_time[i])
print(res)


(n, m, k) = map(int, input().split())
(a, b) = map(int, input().split())
q = list(map(int, input().split()))
q1 = list(map(int, input().split()))
l1 = [[q1[i], q[i]] for i in range(m)]
qq1 = list(map(int, input().split()))
qq2 = list(map(int, input().split()))
l2 = [[0, 0]] + [[qq2[i], qq1[i]] for i in range(k)]
p = 0
li = a
ans = 9999999999999999999
l1 = sorted(l1, key=lambda x: x[0])
for i in range(k, -1, -1):
	v = b - l2[i][0]
	while p != m and v - l1[p][0] >= 0:
		li = min(li, l1[p][1])
		p += 1
	if v >= 0:
		ans = min(ans, max(n - l2[i][1], 0) * li)
print(ans)


def func(i):
	return a[i]
from math import inf
(n, m, k) = map(int, input().split())
(x, mp) = map(int, input().split())
a = [x] + list(map(int, input().split()))
tempcost1 = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
cost2 = [0] + list(map(int, input().split()))
time = inf
i = 0
j = 0
cost1 = [x for (_, x) in sorted(zip(a, tempcost1))]
a.sort()
while i < k + 1 and j < m + 1:
	if cost1[j] + cost2[i] <= mp:
		if (n - b[i]) * a[j] < time:
			time = (n - b[i]) * a[j]
		i += 1
	else:
		j += 1
print(str(time))


import bisect
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]
a.append(x)
b.append(0)
ans = n * x
for i in range(m + 1):
	if b[i] > s:
		continue
	if b[i] + d[0] > s:
		ans = min(ans, n * a[i])
		continue
	t = bisect.bisect_right(d, s - b[i]) - 1
	ans = min(ans, (n - c[t]) * a[i])
print(ans)


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split())) + [x]
b = list(map(int, input().split())) + [0]
c = [0] + list(map(int, input().split()))
d = [0] + list(map(int, input().split()))
arr = sorted(list(zip(a, b)), key=lambda x: -x[1])
ans = n * x
j = 0
for (aa, bb) in arr:
	while j <= k and d[j] + bb <= s:
		j += 1
	if j == 0:
		continue
	ans = min(ans, aa * (n - c[j - 1]))
print(ans)


((n, m, k), (x, s), a, b, c, d) = (list(map(int, input().split())) for _ in ' ' * 6)
a += [x]
b += [0]
c = [0] + c
d = [0] + d
L = sorted(list(zip(a, b)), key=lambda x: -x[1])
(o, j) = (n * x, 0)
for (ai, bi) in L:
	while j <= k and d[j] + bi <= s:
		j += 1
	if j == 0:
		continue
	t = ai * (n - c[j - 1])
	o = min(o, t)
print(o)


from bisect import bisect_right
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = [int(X) for X in input().split()]
b = [int(X) for X in input().split()]
c = [int(X) for X in input().split()]
d = [int(X) for X in input().split()]
tt = bisect_right(d, s)
if tt == 0:
	an = x * n
else:
	an = (n - c[bisect_right(d, s) - 1]) * x
for i in range(m):
	tt = bisect_right(d, s - b[i])
	if tt != 0:
		an = min((n - c[tt - 1]) * a[i], an)
	elif s - b[i] >= 0:
		an = min(an, n * a[i])
print(an)


import bisect
(n, m, k) = [int(i) for i in input().split()]
(x, s) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()] + [x]
b = [int(i) for i in input().split()] + [0]
c = [0] + [int(i) for i in input().split()]
d = [0] + [int(i) for i in input().split()]
time = n * x
for m1 in range(m + 1):
	if b[m1] > s:
		continue
	else:
		t = bisect.bisect_right(d, s - b[m1]) - 1
		time = min(time, (n - c[t]) * a[m1])
if time > 0:
	print(time)
else:
	print('0')


from bisect import bisect_right
(n, m, k) = [int(x) for x in input().split()]
(x, s) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
d = [int(x) for x in input().split()]
ans = n * x
for i in range(m):
	if b[i] <= s:
		cur_s = s - b[i]
		j = bisect_right(d, cur_s) - 1
		if j != -1:
			if (n - c[j]) * a[i] < ans:
				ans = (n - c[j]) * a[i]
		elif n * a[i] < ans:
			ans = n * a[i]
for i in range(k):
	if d[i] <= s:
		if (n - c[i]) * x < ans:
			ans = (n - c[i]) * x
print(ans)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
p = []
for i in range(m):
	p.append([b[i], a[i]])
p.sort()
c = list(map(int, input().split()))
d = list(map(int, input().split()))
j = k - 1
ans = x * n
for i in range(m):
	while j >= 0 and p[i][0] + d[j] > s:
		j -= 1
	if j >= 0:
		ans = min([p[i][1] * (n - c[j]), ans])
	if p[i][0] <= s:
		ans = min([p[i][1] * n, ans])
for j in range(k):
	if d[j] <= s:
		ans = min([x * (n - c[j]), ans])
print(ans)


from bisect import bisect_left, bisect_right
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = n * x
w = bisect_right(d, s) - 1
if 0 <= w < k:
	p = n - c[w]
	if p <= 0:
		print(0)
		exit()
	else:
		ans = min(ans, p * x)
for i in range(m):
	q = s
	e = x
	if b[i] <= s:
		q = s - b[i]
		e = a[i]
	w = bisect_right(d, q) - 1
	p = n
	if 0 <= w < k:
		p = n - c[w]
		if p <= 0:
			print(0)
			exit()
	ans = min(ans, p * e)
print(ans)


(n, m, k) = list(map(int, input().split()))
(x, s) = list(map(int, input().split()))
t = list(map(int, input().split()))
pr = list(map(int, input().split()))
t2 = list(map(int, input().split()))
pr2 = list(map(int, input().split()))
mass1 = []
minans = 10 ** 20
for i in range(m):
	mass1.append((pr[i], t[i]))
mass1.sort()
mass1 = [(0, x)] + mass1
pr2 = [0] + pr2
t2 = [0] + t2
uk1 = len(mass1) - 1
uk2 = 0
maxw = 0
for uk1 in range(len(mass1) - 1, -1, -1):
	if s < mass1[uk1][0]:
		continue
	while uk2 < len(pr2) and mass1[uk1][0] + pr2[uk2] <= s:
		maxw = max(maxw, t2[uk2])
		uk2 += 1
	uk2 -= 1
	minans = min(minans, (n - maxw) * mass1[uk1][1])
print(minans)


from sys import stdin, stdout
(n, m, k) = list(map(int, stdin.readline().split()))
(x, s) = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().split()))
b = list(map(int, stdin.readline().split()))
c = list(map(int, stdin.readline().split()))
d = list(map(int, stdin.readline().split()))
a.insert(0, x)
b.insert(0, 0)
c.insert(0, 0)
d.insert(0, 0)
ans = 1 << 100
for it in range(m + 1):
	mana = s - b[it]
	if mana < 0:
		continue
	(lo, hi) = (0, k)
	while lo != hi:
		mid = (lo + hi + 1) // 2
		if d[mid] <= mana:
			lo = mid
		else:
			hi = mid - 1
	ans = min(ans, (n - c[lo]) * a[it])
stdout.write(str(ans) + '\n')


from __future__ import print_function
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, fl, sl) = gil()
(x, total) = gil()
f = [[bud, sec] for (sec, bud) in zip(gil(), gil())]
s = [[num, bud] for (num, bud) in zip(gil(), gil())]
s.append([0, 0])
f.append([0, x])
f.sort()
for i in range(1, fl + 1):
	f[i][1] = min(f[i][1], f[i - 1][1])
ftop = [f[i][0] for i in range(fl + 1)]
ans = x * n
for (num, bud) in s:
	if bud > total:
		continue
	if num >= n:
		ans = 0
		break
	bud = total - bud
	num = n - num
	idx = bisect_right(ftop, bud) - 1
	ans = min(ans, num * f[idx][1])
print(ans)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
s1 = list(map(int, input().split()))
s1c = list(map(int, input().split()))
s2 = list(map(int, input().split()))
s2c = list(map(int, input().split()))
import bisect
s1.append(x)
s1c.append(0)
s2.insert(0, 0)
s2c.insert(0, 0)
optimum = n * x
for i in range(len(s1)):
	if s1c[i] > s:
		continue
	yu = s - s1c[i]
	o = bisect.bisect_right(s2c, yu, 0, k + 1) - 1
	optimum = min(optimum, (n - s2[o]) * s1[i])
print(optimum)


(potion_nr, speed_spell_nr, instant_spell_nr) = (int(x) for x in input().split())
(base_speed, total_mana) = (int(x) for x in input().split())
speed_spell_idx___speed = [int(x) for x in input().split()]
speed_spell_idx___mana = [int(x) for x in input().split()]
instant_spell_idx___potion_nr = [int(x) for x in input().split()]
instant_spell_idx___mana = [int(x) for x in input().split()]
speed_spell_idx___mana = [0] + speed_spell_idx___mana
speed_spell_idx___speed = [base_speed] + speed_spell_idx___speed
instant_spell_idx___mana = [0] + instant_spell_idx___mana
instant_spell_idx___potion_nr = [0] + instant_spell_idx___potion_nr
best_time = potion_nr * (2 * 10 ** 9 + 1)
for (speed_spell_idx, mana) in enumerate(speed_spell_idx___mana):
	mana_left = total_mana - mana
	curr_speed = speed_spell_idx___speed[speed_spell_idx]
	if mana_left < 0:
		continue
	l = 0
	r = len(instant_spell_idx___mana)
	while r - l > 1:
		m = (l + r) // 2
		mana_cost = instant_spell_idx___mana[m]
		if mana_cost <= mana_left:
			l = m
		else:
			r = m
	best_time = min(best_time, (potion_nr - instant_spell_idx___potion_nr[l]) * curr_speed)
print(best_time)


(n, m, k) = list(map(int, input().split()))
(x, s) = list(map(int, input().split()))
k += 1
m += 1
a = [x] + [int(x) for x in input().split()]
b = [0] + [int(x) for x in input().split()]
c = [0] + [int(x) for x in input().split()]
d = [0] + [int(x) for x in input().split()]
fir = []
for i in range(m):
	fir.append([a[i], b[i]])
fir.sort(key=lambda x: x[1])
ans = n * x
for i in range(m):
	left = s - fir[i][1]
	if left < 0:
		break
	while d[k - 1] > left:
		k -= 1
	now = (n - c[k - 1]) * fir[i][0]
	ans = min(ans, now)
print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m, k) = value()
(x, s) = value()
a = array()
b = array()
c = array()
d = array()
c = [0] + c
d = [-1] + d
time = inf
a = [x] + a
b = [0] + b
for i in range(m + 1):
	have = s - b[i]
	if have < 0:
		continue
	ind = bisect_right(d, have)
	rem = max(0, n - c[ind - 1])
	time = min(time, rem * a[i])
print(time)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
a.append(x)
b.append(0)
ans = x * n
for i in range(m + 1):
	if b[i] <= s:
		l = -1
		r = k
		while l < r - 1:
			y = l + (r - l) // 2
			if d[y] <= s - b[i]:
				l = y
			else:
				r = y
		ans1 = 0
		if l > -1:
			ans1 = a[i] * max(0, n - c[l])
		else:
			ans1 = a[i] * n
		if ans1 < ans:
			ans = ans1
print(ans)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
A = [x] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
D = [0] + list(map(int, input().split()))
QW = list(zip(A, B))
QW.sort(key=lambda x: x[1])
A = [s[0] for s in QW]
B = [s[1] for s in QW]
Res = x * n
for i in range(1, k + 1):
	C[i] = max(C[i], C[i - 1])
l = k
e = 10 ** 19
for i in range(m + 1):
	e = min(e, A[i])
	while l >= 0 and B[i] + D[l] > s:
		l -= 1
	if l >= 0:
		Res = min(Res, max(n - C[l], 0) * A[i])
print(Res)


import sys
input = sys.stdin.readline
from bisect import *
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = [x] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
d = [0] + list(map(int, input().split()))
ans = float('inf')
for i in range(m + 1):
	if b[i] > s:
		continue
	idx = bisect_right(d, s - b[i]) - 1
	ans = min(ans, max(0, (n - c[idx]) * a[i]))
print(ans)


from bisect import *

def ri():
	return map(int, input().split())
(n, m, k) = ri()
(x, s) = ri()
a = list(ri())
b = list(ri())
c = list(ri())
d = list(ri())
a.append(x)
b.append(0)
min_time = n * max(a)
for i in range(m + 1):
	mm = s - b[i]
	if mm >= 0:
		j = bisect_right(d, mm)
		if j > 0:
			min_time = min(min_time, (n - c[j - 1]) * a[i])
		else:
			min_time = min(min_time, n * a[i])
print(min_time)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = n * x
for i in range(m):
	l = 0
	r = k
	while r - l > 1:
		mid = l + (r - l) // 2
		if d[mid] <= s - b[i]:
			l = mid
		else:
			r = mid
	if d[l] <= s - b[i]:
		t = a[i] * (n - c[l])
		ans = min(ans, t)
for i in range(k):
	if d[i] <= s:
		ans = min(ans, x * (n - c[i]))
for i in range(m):
	if b[i] <= s:
		ans = min(ans, a[i] * n)
print(ans)


from bisect import bisect_right

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return i - 1
	return -3
(n, m, k) = list(map(int, input().split()))
(x, s) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = 10 ** 30
for i in range(m):
	if b[i] > s:
		continue
	mana = s - b[i]
	ind = find_le(d, mana)
	if ind == -3:
		ans_i = a[i] * n
	else:
		ans_i = a[i] * max(0, n - c[ind])
	if ans_i < ans:
		ans = ans_i
mana = s
ind = find_le(d, mana)
if ind == -3:
	ans_i = x * n
else:
	ans_i = x * max(0, n - c[ind])
if ans_i < ans:
	ans = ans_i
print(ans)


import bisect
(n, m, k) = [int(i) for i in input().split()]
(x, s) = [int(i) for i in input().split()]
timeOne = [int(i) for i in input().split()]
manaOne = [int(i) for i in input().split()]
numTwo = [int(i) for i in input().split()]
manaTwo = [int(i) for i in input().split()]
timeOne.append(x)
manaOne.append(0)
result = x * n
for i in range(len(timeOne)):
	if manaOne[i] > s:
		continue
	if s - manaOne[i] < manaTwo[0]:
		result = min(result, n * timeOne[i])
		continue
	t = bisect.bisect_right(manaTwo, s - manaOne[i], 0, len(manaTwo)) - 1
	result = min(result, (n - numTwo[t]) * timeOne[i])
print(result)


from bisect import *
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
red = list(map(int, input().split()))
c1 = list(map(int, input().split()))
c1.append(0)
red.append(x)
pot = list(map(int, input().split()))
c2 = list(map(int, input().split()))
from collections import *
al = defaultdict(int)
for i in range(len(c2)):
	al[c2[i]] = pot[i]
total = x * n
for i in range(len(red)):
	if c1[i] <= s:
		left = s - c1[i]
		total = min(total, n * red[i])
		q = bisect_left(c2, left)
		if len(c2) == q:
			q -= 1
		elif c2[q] != left:
			q -= 1
		if q < 0:
			continue
		item = al[c2[q]]
		total = min(max(0, n - item) * red[i], total)
print(total)


def main():
	from sys import stdin, stdout
	import bisect
	(n, m, k) = map(int, stdin.readline().split())
	(x, s) = map(int, stdin.readline().split())
	a = tuple(map(int, stdin.readline().split()))
	b = tuple(map(int, stdin.readline().split()))
	c = tuple(map(int, stdin.readline().split()))
	d = tuple(map(int, stdin.readline().split()))
	myDic = {}
	for i in range(k):
		myDic[d[i]] = max(myDic.get(d[i], 0), c[i])
	time = n * x
	for i in range(m):
		if b[i] <= s:
			index = bisect.bisect_left(d, s - b[i])
			if index:
				reduced = n - myDic[d[index - 1]]
			else:
				reduced = n
			if index < k:
				if d[index] == s - b[i]:
					reduced = n - myDic[d[index]]
			time = min(time, a[i] * reduced)
	for j in myDic:
		if j <= s:
			time = min(time, (n - myDic[j]) * x)
	if time < 0:
		time = 0
	stdout.write(str(time))
main()


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
time = [x] + list(map(int, input().split()))
mana = [0] + list(map(int, input().split()))
potions = [0] + list(map(int, input().split())) + [10 ** 19]
mana2 = [0] + list(map(int, input().split())) + [10 ** 19]
from bisect import bisect_right
ans = 10 ** 19
for i in range(len(time)):
	if mana[i] > s:
		continue
	j = bisect_right(mana2, s - mana[i]) - 1
	rem = n - potions[j]
	ans = min(rem * time[i], ans)
print(ans)


import bisect
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split())) + [x]
b = list(map(int, input().split())) + [0]
c = [0] + list(map(int, input().split()))
d = [0] + list(map(int, input().split()))
l = sorted(list(zip(a, b)), key=lambda x: -x[1])
(ans, j) = (n * x, 0)
for (ai, bi) in l:
	while j <= k and d[j] + bi <= s:
		j += 1
	if j == 0:
		continue
	ans = min(ans, ai * (n - c[j - 1]))
print(ans)


import bisect
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
d = [int(x) for x in input().split()]
ans = n * x
for i in range(m):
	st_potion = a[i]
	nd_potion = 0
	if b[i] > s:
		continue
	if b[i] + d[0] <= s:
		p = bisect.bisect_right(d, s - b[i])
		nd_potion = c[p - 1]
	ans = min(ans, st_potion * (n - nd_potion))
if d[0] <= s:
	p = bisect.bisect_right(d, s)
	nd_potion = c[p - 1]
ans = min(ans, x * (n - nd_potion))
print(ans)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
ma = [int(x) for x in input().split()]
mb = [int(y) for y in input().split()]
ms = [[ma[i], mb[i]] for i in range(m)]
kc = [int(x) for x in input().split()]
kd = [int(x) for x in input().split()]
a = 1
n0 = n
for j in range(k):
	if kd[k - 1 - j] <= s:
		n = n - kc[k - 1 - j]
		break
if n <= 0:
	t = 0
	a = 0
else:
	t = x * n
if a:
	ms.sort(key=lambda a: a[1])
	b = 1
	j = k - 1
	c = 1
	for i in range(m):
		if b:
			if ms[i][1] <= s:
				sr = s - ms[i][1]
				t = min(t, ms[i][0] * n0)
				if c:
					while j != -1 and kd[j] > sr:
						j -= 1
					if j == -1:
						c = 0
					else:
						nr = n0 - kc[j]
						if nr <= 0:
							t = 0
							b = 0
						else:
							t = min(t, ms[i][0] * nr)
			else:
				break
print(t)


import _bisect
(n, m, k) = [int(x) for x in input().split()]
(x, s) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
d = [int(x) for x in input().split()]
a.append(x)
b.append(0)
r = n * x
for i in range(m + 1):
	if b[i] > s:
		continue
	if s - b[i] < d[0]:
		r = min(r, n * a[i])
		continue
	j = _bisect.bisect_right(d, s - b[i], 0, k) - 1
	r = min(r, (n - c[j]) * a[i])
print(r)


import bisect
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a1 = [int(x) for x in input().split()]
a2 = [int(x) for x in input().split()]
b1 = [int(x) for x in input().split()]
b2 = [int(x) for x in input().split()]
a1.append(x)
a2.append(0)
ans = n * x
for i in range(m + 1):
	if a2[i] > s:
		continue
	if s - a2[i] < b2[0]:
		ans = min(ans, n * a1[i])
		continue
	t = bisect.bisect_right(b2, s - a2[i]) - 1
	ans = min(ans, a1[i] * (n - b1[t]))
print(ans)


def max_search(lis, l, r, value):
	if r >= l:
		mid = l + (r - l) // 2
		if lis[mid] > value:
			return max_search(lis, l, mid - 1, value)
		else:
			return max_search(lis, mid + 1, r, value)
	else:
		return l - 1
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
lis1 = [int(item) for item in input().split()]
cost1 = [int(item) for item in input().split()]
lis2 = [int(item) for item in input().split()]
cost2 = [int(item) for item in input().split()]
ans = []
ans.append(x * n)
temp = max_search(cost2, 0, k - 1, s)
if temp >= 0:
	ans.append(x * max(n - lis2[temp], 0))
for i in range(m):
	if cost1[i] <= s:
		x = lis1[i]
		temps = s - cost1[i]
		temp = max_search(cost2, 0, k - 1, temps)
		if temp >= 0:
			ans.append(x * max(n - lis2[temp], 0))
		else:
			ans.append(x * n)
print(min(ans))


def main():
	from bisect import bisect
	(n, m, k) = map(int, input().split())
	(t, s) = map(int, input().split())
	aa = list(map(int, input().split()))
	aa.append(t)
	bb = list(map(int, input().split()))
	bb.append(0)
	cc = [0, *map(int, input().split()), 0]
	dd = [0, *map(int, input().split()), s + 1]
	res = []
	for (t, b) in zip(aa, bb):
		b = s - b
		if b >= 0:
			i = bisect(dd, b)
			if b < dd[i]:
				i -= 1
			x = n - cc[i]
			if x <= 0:
				res = [0]
				break
			res.append(x * t)
	print(min(res))
main()


def R():
	return map(int, input().strip().split())
(n, m, k) = R()
(x, s) = R()
t1 = list(R())
m1 = list(R())
t2 = list(R())
m2 = list(R())
h = []
for i in range(len(m1)):
	if s - m1[i] >= 0:
		h.append([t1[i], s - m1[i]])
h.sort(key=lambda x: x[1])
so_far = None
j = 0
ans = n * x
for i in range(len(h)):
	while j < len(m2) and m2[j] <= h[i][1]:
		so_far = j
		j += 1
	if so_far is not None:
		ans = min(ans, (n - t2[so_far]) * h[i][0])
	ans = min(ans, n * h[i][0])
for i in range(len(m2)):
	if m2[i] <= s:
		ans = min(ans, (n - t2[i]) * x)
print(ans)


import bisect
(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(map(int, input().split()))
z1 = list(zip(a, b))
z2 = list(zip(c, d))
result = n * x
for (ai, bi) in z1:
	if bi > s:
		continue
	current = ai * n
	if current < result:
		result = current
	rest = s - bi
	idx = bisect.bisect_right(d, rest)
	if idx == 0:
		continue
	current = ai * (n - z2[idx - 1][0])
	if current < result:
		result = current
for (ci, di) in z2:
	if di > s:
		continue
	current = x * (n - ci)
	if current < result:
		result = current
print(result)


(n, m, k) = map(int, input().split())
(x, s) = map(int, input().split())
res = n * x
ft = [[0] * 2 for i in range(m)]
st = [[0] * 2 for i in range(k)]
tmparr = list(map(int, input().split()))
for i in range(m):
	ft[i][0] = tmparr[i]
tmparr = list(map(int, input().split()))
for i in range(m):
	ft[i][1] = tmparr[i]
tmparr = list(map(int, input().split()))
for i in range(k):
	st[i][0] = tmparr[i]
tmparr = list(map(int, input().split()))
for i in range(k):
	st[i][1] = tmparr[i]
for i in range(m):
	nows = s - ft[i][1]
	if nows < 0:
		continue
	nowr = n * ft[i][0]
	if nows >= st[0][1]:
		l = 0
		r = k
		while r - l > 1:
			m = (l + r) // 2
			if st[m][1] <= nows:
				l = m
			else:
				r = m
		nowr -= ft[i][0] * st[l][0]
	res = min(res, nowr)
for i in range(k):
	if st[i][1] <= s:
		res = min(res, x * (n - st[i][0]))
print(res)


import bisect

def anton_and_magic_potions():
	(no_potions, no_fst_spell, no_snd_spell) = [int(x) for x in input().split(' ')]
	(initial_time, mana) = [int(x) for x in input().split(' ')]
	first_spell = [int(x) for x in input().split(' ')]
	mana_first_spell = [int(x) for x in input().split(' ')]
	potions_second_spell = [int(x) for x in input().split(' ')]
	mana_second_spell = [int(x) for x in input().split(' ')]
	first_spell.append(initial_time)
	mana_first_spell.append(0)
	total_time = no_potions * initial_time
	for i in range(no_fst_spell + 1):
		if mana_first_spell[i] > mana:
			continue
		pos2 = bisect.bisect_right(mana_second_spell, mana - mana_first_spell[i]) - 1
		if pos2 >= 0:
			no_potions2 = no_potions - potions_second_spell[pos2]
			res = no_potions2 * first_spell[i]
		else:
			res = no_potions * first_spell[i]
		total_time = min(total_time, res)
	print(total_time)
anton_and_magic_potions()


from sys import stdin
from sys import stdout
(n, m, k) = (int(x) for x in stdin.readline()[:-1].split())
(x, s) = (int(x) for x in stdin.readline()[:-1].split())
a = [int(x) for x in stdin.readline()[:-1].split()]
b = [int(x) for x in stdin.readline()[:-1].split()]
c = [int(x) for x in stdin.readline()[:-1].split()]
d = [int(x) for x in stdin.readline()[:-1].split()]
c.reverse()
d.reverse()
spell1 = sorted(zip(b, a))
massimi = []
for i in range(len(spell1)):
	if spell1[i][0] <= s and (i == 0 or spell1[i][1] < massimi[i - 1]):
		massimi.append(spell1[i][1])
	elif i != 0 and (spell1[i][0] > s or spell1[i][1] >= massimi[i - 1]):
		massimi.append(massimi[i - 1])
	else:
		massimi.append(x)
ans = n * massimi[-1]
last = 0
for (di, ci) in zip(d, c):
	low = last
	high = len(spell1)
	mid = (high + low) // 2
	delta = s - di
	if delta < 0:
		continue
	index = -1
	while high - low > 1:
		if spell1[mid][0] > delta:
			high = mid - 1
			mid = (high + low) // 2
		elif spell1[mid][0] <= delta and mid == len(spell1) - 1 or (spell1[mid][0] <= delta and spell1[mid + 1][0] > delta):
			index = mid
			break
		elif spell1[mid][0] <= delta and spell1[mid + 1][0] <= delta:
			low = mid
			mid = (high + low) // 2
	if high - low == 1:
		if 0 <= high < m and spell1[high][0] <= delta:
			index = high
		elif 0 <= low < m and spell1[low][0] <= delta:
			index = low
	elif high - low == 0 and spell1[low][0] <= delta:
		index = low
	tentativo = ans
	if index == -1:
		tentativo = (n - ci) * x
	else:
		tentativo = (n - ci) * massimi[index]
	if tentativo < ans:
		ans = tentativo
	last = index if index > -1 else 0
stdout.write(str(ans))


def main():
	(n, m, k) = map(int, input().split())
	(x, s) = map(int, input().split())
	a = input().split()
	b = input().split()
	c = input().split()
	d = input().split()
	type_1 = []
	for i in range(m):
		type_1.append((int(b[i]), int(a[i])))
	type_1.sort()
	best = n * x
	maxi = [0] * k
	for i in range(k):
		maxi[i] = int(c[i])
		if i > 0:
			maxi[i] = max(maxi[i], maxi[i - 1])
		if int(d[i]) <= s:
			best = min(best, max(0, n - maxi[i]) * x)
	pos = k - 1
	for i in range(m):
		while pos >= 0 and type_1[i][0] + int(d[pos]) > s:
			pos -= 1
		if type_1[i][0] <= s:
			if pos >= 0:
				best = min(best, max(0, n - maxi[pos]) * type_1[i][1])
			else:
				best = min(best, n * type_1[i][1])
	print(best)
main()


(n, m, k) = map(int, input().split())
(X, S) = map(int, input().split())
a = [X] + [*map(int, input().split())]
b = [0] + [*map(int, input().split())]
c = [0] + [*map(int, input().split())]
d = [0] + [*map(int, input().split())]
from bisect import bisect as bis
result = 100000000000000000000
for (x, y) in zip(a, b):
	s = S - y
	item = bis(d, s)
	res = n * X
	if item == 0:
		if d[0] <= s:
			res = max(0, n - c[0]) * x
	else:
		item -= 1
		if d[item] <= s:
			res = max(0, n - c[item]) * x
	result = min(res, result)
print(result)


s = input()
s1 = s.split()
tot = int(s1[0])
s = input()
s1 = s.split()
time = int(s1[0])
mon = int(s1[1])
s = input()
s1 = s.split()
p1 = [int(i) for i in s1]
s = input()
s1 = s.split()
p1cost = [int(i) for i in s1]
s = input()
s1 = s.split()
p2 = [int(i) for i in s1]
s = input()
s1 = s.split()
p2cost = [int(i) for i in s1]

def fun(cost):
	global p2
	global p2cost
	l = 0
	r = len(p2) - 1
	while l < r:
		mid = (l + r + 1) // 2
		if p2cost[mid] > cost:
			r = mid - 1
		else:
			l = mid
	mid = (l + r + 1) // 2
	if p2cost[mid] > cost:
		return 0
	else:
		return p2[mid]
minval = tot * time
for i in range(len(p1)):
	if p1cost[i] <= mon:
		minval = min(minval, (tot - fun(mon - p1cost[i])) * p1[i])
minval = min(minval, (tot - fun(mon)) * time)
print(minval)


import bisect
(N, M, K) = map(int, input().split())
(X, S) = map(int, input().split())
ax = [int(x) for x in input().split()]
bx = [int(x) for x in input().split()]
cx = [int(x) for x in input().split()]
dx = [int(x) for x in input().split()]

def find_best(mana_left, costs):
	idx = bisect.bisect_right(costs, mana_left)
	return max(0, min(idx - 1, len(costs) - 1))
zero_best = find_best(S, dx)
if dx[zero_best] > S:
	sol = N * X
else:
	sol = (N - cx[zero_best]) * X
for i in range(M):
	mana_left = S - bx[i]
	if mana_left > 0:
		j = find_best(mana_left, dx)
		if dx[j] > mana_left:
			sol = min(sol, ax[i] * N)
		else:
			sol = min(sol, ax[i] * (N - cx[j]))
	elif mana_left == 0:
		sol = min(sol, ax[i] * N)
print(sol)


import bisect
(n, s1, s2) = [int(x) for x in input().split()]
(it, m) = [int(x) for x in input().split()]
s1t = [int(x) for x in input().split()]
s1m = [int(x) for x in input().split()]
s2p = [int(x) for x in input().split()]
s2m = [int(x) for x in input().split()]
s1t.append(it)
s1m.append(0)
mt = it * n
for i in range(s1 + 1):
	if s1m[i] <= m:
		ind = bisect.bisect(s2m, m - s1m[i])
		if ind == 0:
			mt = min(mt, n * s1t[i])
		else:
			if n - s2p[ind - 1] <= 0:
				mt = 0
				break
			mt = min((n - s2p[ind - 1]) * s1t[i], mt)
print(mt)


import bisect
((n, m, k), (x, s), a, b, c, d) = (list(map(int, input().split())) for _ in ' ' * 6)
a += [x]
b += [0]
ans = n * x
for i in range(m + 1):
	if b[i] <= s:
		j = bisect.bisect(d, s - b[i])
		if j == 0:
			t = a[i] * n
			ans = min(ans, t)
		else:
			t = a[i] * (n - c[j - 1])
			ans = min(ans, t)
print(ans)


from sys import stdin
from bisect import bisect
input = stdin.readline

def magic(n, time, points, spell1, spell2):
	ans = float('inf')
	spell1 = spell1 + [(time, 0)]
	spell2 = [(0, 0)] + spell2
	dp = [float('inf')] * len(spell1)
	for i in range(0, len(spell1)):
		pointer = bisect(spell2, (points - spell1[i][1], 2000020000))
		if pointer:
			ans = min(ans, max(0, n - spell2[pointer - 1][1]) * spell1[i][0])
	return ans
(n, x, s) = map(int, input().strip().split())
(time, points) = map(int, input().strip().split())
spell1 = list(map(int, input().strip().split()))
spell1c = list(map(int, input().strip().split()))
spell2 = list(map(int, input().strip().split()))
spell2c = list(map(int, input().strip().split()))
spell1 = list(zip(spell1, spell1c))
spell2 = list(zip(spell2c, spell2))
print(magic(n, time, points, spell1, spell2))


def binSearch(array, lo, hi, target):
	mid = lo + (hi - lo) // 2
	if lo >= hi:
		if array[mid] <= target:
			return mid
		return mid - 1
	if array[mid] <= target:
		return binSearch(array, mid + 1, hi, target)
	return binSearch(array, lo, mid, target)
(potions, first, second) = map(int, input().split())
(preparationTime, mana) = map(int, input().split())
first = list(map(int, input().split()))
manaFirst = list(map(int, input().split()))
second = list(map(int, input().split()))
manaSecond = list(map(int, input().split()))
time = preparationTime * potions
buyThis = binSearch(manaSecond, 0, len(second) - 1, mana)
if buyThis != -1:
	time = min(time, preparationTime * (potions - second[buyThis]))
for i in range(len(first)):
	(magic, cost) = (first[i], manaFirst[i])
	if cost <= mana:
		buyThis = binSearch(manaSecond, 0, len(second) - 1, mana - cost)
		if buyThis == -1:
			time = min(time, magic * potions)
		else:
			time = min(time, magic * (potions - second[buyThis]))
print(time)