The Government of Mars is not only interested in optimizing space flights, but also wants to improve the road system of the planet.

One of the most important highways of Mars connects Olymp City and Kstolop, the capital of Cydonia. In this problem, we only consider the way from Kstolop to Olymp City, but not the reverse path (i. e. the path from Olymp City to Kstolop).

The road from Kstolop to Olymp City is $\ell$ kilometers long. Each point of the road has a coordinate $x$ ($0 \le x \le \ell$), which is equal to the distance from Kstolop in kilometers. So, Kstolop is located in the point with coordinate $0$, and Olymp City is located in the point with coordinate $\ell$.

There are $n$ signs along the road, $i$-th of which sets a speed limit $a_i$. This limit means that the next kilometer must be passed in $a_i$ minutes and is active until you encounter the next along the road. There is a road sign at the start of the road (i. e. in the point with coordinate $0$), which sets the initial speed limit.

If you know the location of all the signs, it's not hard to calculate how much time it takes to drive from Kstolop to Olymp City. Consider an example:

Here, you need to drive the first three kilometers in five minutes each, then one kilometer in eight minutes, then four kilometers in three minutes each, and finally the last two kilometers must be passed in six minutes each. Total time is $3\cdot 5 + 1\cdot 8 + 4\cdot 3 + 2\cdot 6 = 47$ minutes.

To optimize the road traffic, the Government of Mars decided to remove no more than $k$ road signs. It cannot remove the sign at the start of the road, otherwise, there will be no limit at the start. By removing these signs, the Government also wants to make the time needed to drive from Kstolop to Olymp City as small as possible.

The largest industrial enterprises are located in Cydonia, so it's the priority task to optimize the road traffic from Olymp City. So, the Government of Mars wants you to remove the signs in the way described above.


-----Input-----

The first line contains three integers $n$, $\ell$, $k$ ($1 \le n \le 500$, $1 \le \ell \le 10^5$, $0 \le k \le n-1$), the amount of signs on the road, the distance between the cities and the maximal number of signs you may remove.

The second line contains $n$ integers $d_i$ ($d_1 = 0$, $d_i < d_{i+1}$, $0 \le d_i \le \ell - 1$) — coordinates of all signs.

The third line contains $n$ integers $a_i$ ($1 \le a_i \le 10^4$) — speed limits.


-----Output-----

Print a single integer — minimal possible time to drive from Kstolop to Olymp City in minutes, if you remove no more than $k$ road signs.


-----Examples-----

Input
4 10 0
0 3 4 8
5 8 3 6
Output
47
Input
4 10 2
0 3 4 8
5 8 3 6
Output
38


-----Note-----

In the first example, you cannot remove the signs. So the answer is $47$, as it's said in the statements above.

In the second example, you may remove the second and the fourth sign. In this case, you need to drive four kilometers in $4\cdot5 = 20$ minutes, and then six kilometers in $6\cdot3 = 18$, so the total time is $4\cdot5 + 6\cdot3 = 38$ minutes.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import functools
import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def read():
	return list(map(int, input().strip().split()))

def solve(l, k, d, a):
	d.append(l)

	@functools.lru_cache(maxsize=None)
	def solve_rec(position, drops, speed):
		if position >= len(a):
			return 0
		res = MAX
		if drops > 0 and a[position] > speed:
			res = min(res, speed * (d[position + 1] - d[position]) + solve_rec(position + 1, drops - 1, speed))
		res = min(res, a[position] * (d[position + 1] - d[position]) + solve_rec(position + 1, drops, a[position]))
		return res
	return solve_rec(0, k, a[0])
(n, l, k) = read()
d = read()
a = read()
print(solve(l, k, d, a))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
mul = lambda : map(int, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))

def f(n, k, l, d, a):
	dp = {}

	def sol(i, k, s):
		if i >= n:
			return 0
		if dp.get((i, k, s)) != None:
			return dp[i, k, s]
		t = (d[i + 1] - d[i]) * a[i] + sol(i + 1, k, a[i])
		if k > 0 and a[i] > s:
			t = min((d[i + 1] - d[i]) * s + sol(i + 1, k - 1, s), t)
		dp[i, k, s] = t
		return t
	ans = (d[1] - d[0]) * a[0] + sol(1, k, a[0])
	print(ans)
(n, l, k) = mul()
d = seq()
a = seq()
d.append(l)
f(n, k, l, d, a)


import collections

def problem3(n, l, k, distance, speedLimit):
	memo = collections.defaultdict(int)

	def topdownDP(idx, numSings, v):
		if numSings < 0:
			return float('inf')
		if idx == n:
			return 0
		if (idx, numSings, v) in memo:
			return memo[idx, numSings, v]
		if idx == 0:
			memo[idx, numSings, v] = (distance[idx + 1] - distance[idx]) * v + topdownDP(idx + 1, numSings, v)
		elif speedLimit[idx] < v:
			memo[idx, numSings, v] = (distance[idx + 1] - distance[idx]) * speedLimit[idx] + topdownDP(idx + 1, numSings, speedLimit[idx])
		else:
			memo[idx, numSings, v] = min((distance[idx + 1] - distance[idx]) * speedLimit[idx] + topdownDP(idx + 1, numSings, speedLimit[idx]), (distance[idx + 1] - distance[idx]) * v + topdownDP(idx + 1, numSings - 1, v))
		return memo[idx, numSings, v]
	print(topdownDP(0, k, speedLimit[0]))
(n, l, k) = [int(num) for num in input().split(' ')]
distance = [int(num) for num in input().split(' ')]
distance.append(l)
speedLimit = [int(num) for num in input().split(' ')]
problem3(n, l, k, distance, speedLimit)


(n, l, k) = map(int, input().split())
a = list(map(int, input().split())) + [l]
b = list(map(int, input().split())) + [0]
dp = {}

def dfs(i, k, p):
	if (i, k, p) in dp:
		return dp[i, k, p]
	if i == n:
		return 0
	res = float('inf')
	if k > 0 and b[i] > p:
		res = min(res, p * (a[i + 1] - a[i]) + dfs(i + 1, k - 1, p))
	res = min(res, b[i] * (a[i + 1] - a[i]) + dfs(i + 1, k, b[i]))
	dp[i, k, p] = res
	return res
print(a[1] * b[0] + dfs(1, k, b[0]))


import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache

def solve(l, k, d, a):
	d.append(l)

	@lru_cache(maxsize=None)
	def dp(pos, k, speed):
		if pos >= len(a):
			return 0
		res = float('inf')
		if k > 0 and a[pos] > speed:
			res = min(res, speed * (d[pos + 1] - d[pos]) + dp(pos + 1, k - 1, speed))
		res = min(res, a[pos] * (d[pos + 1] - d[pos]) + dp(pos + 1, k, a[pos]))
		return res
	return dp(0, k, a[0])
(n, l, k) = map(int, input().split())
d = list(map(int, input().split()))
a = list(map(int, input().split()))
print(solve(l, k, d, a))


(n, l, k) = map(int, input().split())
second = list(map(int, input().split())) + [l]
third = list(map(int, input().split())) + [0]
dict = {}

def dfs(i, k, p):
	if (i, k, p) in dict:
		return dict[i, k, p]
	if i == n:
		return 0
	result = float('inf')
	if k > 0 and third[i] > p:
		result = min(result, p * (second[i + 1] - second[i]) + dfs(i + 1, k - 1, p))
	result = min(result, third[i] * (second[i + 1] - second[i]) + dfs(i + 1, k, third[i]))
	dict[i, k, p] = result
	return result
print(second[1] * third[0] + dfs(1, k, third[0]))


import threading
import sys
sys.setrecursionlimit(10 ** 6)

def main():
	(n, l, k) = map(int, input().split())
	a = list(map(int, input().split())) + [l]
	b = list(map(int, input().split())) + [0]
	dp = {}

	def dfs(i, k, p):
		if (i, k, p) in dp:
			return dp[i, k, p]
		if i == n:
			return 0
		res = float('inf')
		if k > 0 and b[i] > p:
			res = min(res, p * (a[i + 1] - a[i]) + dfs(i + 1, k - 1, p))
		res = min(res, b[i] * (a[i + 1] - a[i]) + dfs(i + 1, k, b[i]))
		dp[i, k, p] = res
		return res
	print(a[1] * b[0] + dfs(1, k, b[0]))
threading.stack_size(10 ** 6)
t = threading.Thread(target=main)
t.start()
t.join()


(n, l, k) = map(int, input().split())
coor = list(map(int, input().split())) + [l]
limits = list(map(int, input().split())) + [0]
memo = {}

def dfs(i, k, s):
	if (i, k, s) in memo:
		return memo[i, k, s]
	if i == len(coor) - 1:
		return 0
	res = float('inf')
	if i == 0:
		res = (coor[i + 1] - coor[i]) * limits[i] + dfs(i + 1, k, limits[i])
	elif k > 0 and limits[i] > s:
		take = (coor[i + 1] - coor[i]) * s + dfs(i + 1, k - 1, s)
		leave = (coor[i + 1] - coor[i]) * limits[i] + dfs(i + 1, k, limits[i])
		res = min(take, leave)
	else:
		leave = (coor[i + 1] - coor[i]) * limits[i] + dfs(i + 1, k, limits[i])
		res = leave
	memo[i, k, s] = res
	return memo[i, k, s]
print(dfs(0, k, None))


import functools
import sys
input = sys.stdin.readline

def read():
	return list(map(int, input().strip().split()))

def solve(l, k, d, a):
	d.append(l)
	cache = {}

	def solve_rec(position, drops, speed):
		if (position, drops, speed) in cache:
			return cache[position, drops, speed]
		if position >= len(a):
			return 0
		res = float('inf')
		if drops > 0 and a[position] > speed:
			res = min(res, speed * (d[position + 1] - d[position]) + solve_rec(position + 1, drops - 1, speed))
		res = min(res, a[position] * (d[position + 1] - d[position]) + solve_rec(position + 1, drops, a[position]))
		cache[position, drops, speed] = res
		return res
	return d[1] * a[0] + solve_rec(1, k, a[0])
(n, l, k) = read()
d = read()
a = read()
print(solve(l, k, d, a))