Alan decided to get in shape for the summer, so he created a precise workout plan to follow. His plan is to go to a different gym every day during the next N days and lift $X[i]$ grams on day $i$. In order to improve his workout performance at the gym, he can buy exactly one pre-workout drink at the gym he is currently in and it will improve his performance by $A$ grams permanently and immediately. In different gyms these pre-workout drinks can cost different amounts $C[i]$ because of the taste and the gym's location but its permanent workout gains are the same. Before the first day of starting his workout plan, Alan knows he can lift a maximum of $K$ grams. Help Alan spend a minimum total amount of money in order to reach his workout plan. If there is no way for him to complete his workout plan successfully output $-1$.


-----Input-----

The first one contains two integer numbers, integers $N$ $(1 \leq N \leq 10^5)$ and $K$ $(1 \leq K \leq 10^5)$ – representing number of days in the workout plan and how many grams he can lift before starting his workout plan respectively. The second line contains $N$ integer numbers $X[i]$ $(1 \leq X[i] \leq 10^9)$ separated by a single space representing how many grams Alan wants to lift on day $i$. The third line contains one integer number $A$ $(1 \leq A \leq 10^9)$ representing permanent performance gains from a single drink. The last line contains $N$ integer numbers $C[i]$ $(1 \leq C[i] \leq 10^9)$ , representing cost of performance booster drink in the gym he visits on day $i$.


-----Output-----

One integer number representing minimal money spent to finish his workout plan. If he cannot finish his workout plan, output -1.


-----Examples-----
Input
5 10000
10000 30000 30000 40000 20000
20000
5 2 8 3 6

Output
5

Input
5 10000
10000 40000 30000 30000 20000
10000
5 2 8 3 6

Output
-1



-----Note-----

First example: After buying drinks on days 2 and 4 Alan can finish his workout plan. Second example: Alan cannot lift 40000 grams on day 2.

Source: codeforces | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms


Solutions:
import sys, heapq
input = lambda : sys.stdin.readline().strip('\r\n')
(n, k) = map(int, input().split())
x = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
heap = []
ans = 0
for i in range(n):
	heapq.heappush(heap, c[i])
	while x[i] > k and len(heap) > 0:
		k += a
		ans += heapq.heappop(heap)
	if k < x[i]:
		print(-1)
		exit()
print(ans)


import heapq
(n, initial) = map(int, input().split())
target = list(map(int, input().split()))
gain = int(input())
prices = list(map(int, input().split()))
flag = True
for i in range(n):
	if target[i] > (i + 1) * gain + initial:
		flag = False
		print(-1)
		break
if flag:
	a = [10 ** 18]
	heapq.heapify(a)
	maxx = -1
	ans = 0
	for i in range(n):
		heapq.heappush(a, prices[i])
		if target[i] > initial:
			moves = (target[i] - initial - 1) // gain + 1
			if moves == 0:
				break
			else:
				for i in range(moves):
					ans += heapq.heappop(a)
					initial += gain
	print(ans)


import heapq
(n, k) = map(int, input().split())
des = list(map(int, input().split()))
g = int(input())
cost = list(map(int, input().split()))
cos = 0
flag = 0
cur = k
dec = {}
hp = []
heapq.heapify(hp)
for i in range(n):
	dec[i] = 0
for i in range(n):
	if k + g * (i + 1) < des[i]:
		flag = 1
		break
	else:
		heapq.heappush(hp, cost[i])
		while cur < des[i]:
			cur += g
			cos += heapq.heappop(hp)
if flag == 1:
	print(-1)
else:
	print(cos)


from math import ceil
from collections import deque
import heapq as heap
(n, k) = [int(p) for p in input().split()]
arr = deque([int(p) for p in input().split()])
a = int(input())
cost = deque([int(p) for p in input().split()])
temp = []
heap.heapify(temp)
total = 0
ok = 1
for i in range(n):
	heap.heappush(temp, cost[i])
	while arr[i] > k and temp:
		k += a
		total += heap.heappop(temp)
	if k < arr[i]:
		ok = 0
		break
if ok:
	print(total)
else:
	print(-1)


import sys
from queue import PriorityQueue
(n, k) = map(int, input().split())
t = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
f = 1
cost = 0
m_q = PriorityQueue()
for i in range(n):
	if k + a * (i + 1) < t[i]:
		print(-1)
		break
else:
	for j in range(n):
		if k < t[j]:
			m_q.put(c[j])
			while m_q.qsize() > 0:
				cost += m_q.get()
				k = k + a
				if k >= t[j]:
					break
		else:
			m_q.put(c[j])
	print(cost)


from heapq import *
(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
cur = []
res = 0
for (i, p) in enumerate(arr):
	heappush(cur, c[i])
	if p <= k:
		continue
	if len(cur) * a + k < p:
		print(-1)
		return
	while p > k:
		res += heappop(cur)
		k += a
print(res)


import heapq

def solve(n, k, x, a, c):
	heap = []
	cost = 0
	for i in range(n):
		heapq.heappush(heap, c[i])
		if x[i] > k:
			while k < x[i]:
				if len(heap) == 0:
					return -1
				cost += heapq.heappop(heap)
				k += a
	return cost
(n, k) = list(map(int, input().split()))
x = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
print(solve(n, k, x, a, c))


import math
import heapq

def solve_workout(n_days, strength, plan, gain, costs):
	total_cost = 0
	heap = list()
	for i in range(n_days):
		heapq.heappush(heap, costs[i])
		n_doses = int(math.ceil((plan[i] - strength) / gain))
		while n_doses > 0 and heap:
			total_cost += heapq.heappop(heap)
			strength += gain
			n_doses -= 1
		if strength < plan[i]:
			return -1
	return total_cost

def __starting_point():
	(N, K) = tuple(map(int, input().split()))
	X = list(map(int, input().split()))
	A = int(input())
	C = list(map(int, input().split()))
	print(solve_workout(N, K, X, A, C))
__starting_point()


import heapq

class Input:

	def __init__(self):
		from sys import stdin
		lines = stdin.readlines()
		self.lines = list([line.rstrip('\n') for line in reversed(lines) if line != '\n'])

	def input(self):
		return self.lines.pop()

	def input_int_list(self):
		return list(map(int, self.input().split()))

	def __bool__(self):
		return bool(self.lines)

def workout_plan(n, k, xs, a, cs):
	choices = []
	cs.reverse()
	total_cost = 0
	for x in xs:
		heapq.heappush(choices, cs.pop())
		while k < x:
			if choices:
				k += a
				total_cost += heapq.heappop(choices)
			else:
				return -1
	return total_cost
inp = Input()
(n, k) = inp.input_int_list()
xs = inp.input_int_list()
a = int(inp.input())
cs = inp.input_int_list()
print(workout_plan(n, k, xs, a, cs))


import heapq

def smaller_by_1(num):
	return num - 1

def main():
	(N, k) = list(map(int, input().split(' ')))
	X = list(map(int, input().split(' ')))
	A = int(input())
	C = list(map(int, input().split(' ')))
	money_needed = 0
	drinks_needed = []
	drunk_to_now = 0
	for i in range(N):
		objective = X[i]
		drinks_needed.append((objective - k + A - 1) // A)
	possible_drinks = []
	for i in range(len(drinks_needed)):
		heapq.heappush(possible_drinks, C[i])
		if drinks_needed[i] - drunk_to_now <= 0:
			continue
		else:
			while drinks_needed[i] - drunk_to_now != 0:
				if len(possible_drinks) == 0:
					print(-1)
					return 0
				else:
					money_needed += heapq.heappop(possible_drinks)
					drunk_to_now += 1
	print(money_needed)
main()


from queue import PriorityQueue
(n, k) = map(int, input().split())
x = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
tot = 0
pq = PriorityQueue()
for i in range(0, n):
	if k >= x[i]:
		pq.put(c[i])
	else:
		pq.put(c[i])
		while pq.qsize():
			ans = pq.get()
			k += a
			tot += ans
			if k >= x[i]:
				break
		if k < x[i]:
			tot = -1
			break
print(tot)


import heapq as hp
R = lambda : map(int, input().split())
(n, k) = R()
xs = list(R())
(a, r, h) = (int(input()), 0, [])
cs = list(R())
for (i, x) in enumerate(xs):
	hp.heappush(h, cs[i])
	while x > k and h:
		s = hp.heappop(h)
		k += a
		r += s
	if x > k:
		r = -1
		break
print(r)


(N, K) = map(int, input().split())
X = list(map(int, input().split()))
A = int(input())
C = list(map(int, input().split()))
available_drinks = []
total_cost = 0
ability = K
for i in range(N):
	available_drinks.append(C[i])
	if ability < X[i]:
		drinks_needed = (X[i] - ability - 1) // A + 1
		if drinks_needed > len(available_drinks):
			print(-1)
			break
		available_drinks.sort()
		total_cost += sum(available_drinks[:drinks_needed])
		available_drinks = available_drinks[drinks_needed:]
		ability += A * drinks_needed
else:
	print(total_cost)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(1):
		(n, k) = ria()
		x = ria()
		a = ri()
		c = ria()
		mcum = []
		heapmcum = heapify(mcum)
		m = 9999999999999999999999
		spent = 0
		for i in range(n):
			cost = 0
			heappush(mcum, c[i])
			if k < x[i]:
				while k < x[i]:
					if len(mcum) == 0:
						spent = -1
						break
					cost += heappop(mcum)
					k += a
			if spent == -1:
				break
			spent += cost
		print(spent)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			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, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			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()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

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

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import heapq

def process(n, k, X, a, C):
	res = 0
	A = []
	for i in range(len(X)):
		heapq.heappush(A, C[i])
		if k + len(A) * a < X[i]:
			return -1
		else:
			while k < X[i]:
				res += heapq.heappop(A)
				k += a
	return res
(n, k) = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
a = int(input())
C = [int(x) for x in input().split()]
print(process(n, k, X, a, C))


import heapq as hp
(N, K) = map(int, input().split())
X = list(map(int, input().split()))
A = int(input())
C = list(map(int, input().split()))
limit = K
q = []
cost = 0
for (i, x) in enumerate(X):
	hp.heappush(q, C[i])
	if x > limit:
		while limit < x and q:
			limit += A
			nc = hp.heappop(q)
			cost += nc
		if limit < x:
			cost = -1
			break
print(cost)


import heapq

def main():
	(n, k) = readIntArr()
	X = readIntArr()
	A = int(input())
	C = readIntArr()
	ok = True
	costs = []
	ans = 0
	for i in range(n):
		heapq.heappush(costs, C[i])
		while k < X[i]:
			if len(costs) == 0:
				ok = False
				break
			k += A
			ans += heapq.heappop(costs)
	if ok:
		print(ans)
	else:
		print(-1)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


R = lambda : map(int, input().split())
(n, k) = R()
xs = list(R())
a = int(input())
cs = list(R())
r = j = 0
try:
	for (i, x) in enumerate(xs):
		while x > k:
			s = min(cs[:i + 1 - j])
			cs.remove(s)
			j += 1
			k += a
			r += s
except:
	print(-1)
	quit()
print(r)


import sys
import os
from io import BytesIO, IOBase

def cel(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return defaultdict(int)

def ddl():
	return defaultdict(list)

def ddd():
	return defaultdict(defaultdict(int))
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')
from collections import defaultdict
from heapq import *
from queue import PriorityQueue
(n, k) = mi()
X = li()
A = ii()
C = li()
ans = 0
cost = []
for i in range(n):
	req = (X[i] - k) // A + ((X[i] - k) % A != 0)
	heappush(cost, C[i])
	if req > len(cost):
		ans = -1
		break
	else:
		for j in range(req):
			ans += heappop(cost)
			k += A
print(ans)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
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')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, k) = mp()
arr = lmp()
a = iinp()
cost = lmp()
hp = []
ans = 0
flg = True
for i in range(n):
	heappush(hp, cost[i])
	while hp and k < arr[i]:
		k += a
		ans += heappop(hp)
	if k < arr[i]:
		flg = False
		break
print(ans if flg else -1)


import sys, math
from heapq import heappush, heappop
readline = sys.stdin.readline
mr = lambda : map(int, readline().split())
(n, k) = mr()
tmp = list(mr())
a = int(readline())
cost = list(mr())
for i in range(n):
	tmp[i] -= k
buyIndexes = []
energy = 0
ans = 0
for i in range(n):
	heappush(buyIndexes, cost[i])
	if energy < tmp[i]:
		ordered = []
		while energy < tmp[i]:
			energy += a
			if len(buyIndexes) == 0:
				ans = -1
				break
			ans += heappop(buyIndexes)
	if ans == -1:
		break
print(ans)


import heapq
import sys
(n, k) = map(int, input().split())
l = k
arr = list(map(int, input().split()))
add = int(input())
price = list(map(int, input().split()))
ans = 0
size = 0
s = [9999999999999999999]
heapq.heapify(s)
for i in range(n):
	heapq.heappush(s, price[i])
	size += 1
	if arr[i] > l:
		b = (arr[i] - l - 1) // add + 1
		if size < b:
			print(-1)
			sys.exit()
		else:
			if b == 0:
				break
			for j in range(b):
				ans += heapq.heappop(s)
				l += add
				size -= 1
print(ans)


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 10 ** 10 + 7
(n, k) = R()
(*a,) = R()
x = I()
(*p,) = R()
v = []
pwr = k
ans = 0
for i in range(n):
	v += (p[i],)
	v.sort(reverse=True)
	while pwr < a[i] and v:
		pwr += x
		ans += v.pop()
	if pwr < a[i]:
		exit(print(-1))
print(ans)


import sys
input = sys.stdin.readline
from heapq import *
(n, k) = map(int, input().split())
lis = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
cost = 0
q = []
for i in range(n):
	heappush(q, c[i])
	while q and lis[i] > k:
		k += a
		cost += heappop(q)
	if lis[i] > k:
		cost = -1
		break
print(cost)


import heapq
(n, k) = list(map(int, input().split()))
x = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
out = 0
f = 0
minv = []
for i in range(n):
	heapq.heappush(minv, c[i])
	while k < x[i] and minv:
		k += a
		out += heapq.heappop(minv)
	if k < x[i]:
		f = 1
		break
if f == 1:
	print(-1)
else:
	print(out)


(n, k) = map(int, input().split())
P = list(map(int, input().split()))
from heapq import *
A = int(input())
c = list(map(int, input().split()))
cur = []
cost = 0
for (i, p) in enumerate(P):
	heappush(cur, c[i])
	if p > k:
		if len(cur) * A + k < p:
			cost = -1
			break
		else:
			while p > k:
				cost += heappop(cur)
				k += A
print(cost)


from queue import PriorityQueue
(N, K) = tuple(map(int, input().split()))
X = list(map(int, input().split()))
A = int(input())
C = list(map(int, input().split()))
m_q = PriorityQueue()
m = 0
for i in range(N):
	if K < X[i]:
		m_q.put(C[i])
		while m_q.qsize() > 0:
			K += A
			m += m_q.get()
			if K >= X[i]:
				break
		if K < X[i]:
			m = -1
			break
	else:
		m_q.put(C[i])
print(m)


import os
import sys
from io import BytesIO, IOBase
from heapq import *

def main():
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	a = int(input())
	c = list(map(int, input().split()))
	b = []
	ans = 0
	for i in range(n):
		heappush(b, c[i])
		while b and k < w[i]:
			k += a
			ans += heappop(b)
		if k < w[i]:
			ans = -1
			break
	print(ans)
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')
main()


from math import ceil
from heapq import heappush, heapify, heappop
(n, x) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
a = int(input())
c = [int(i) for i in input().split()]
for i in range(n):
	l[i] = ceil((l[i] - x) / a)
cost = 0
flag = True
heap = []
till = 0
for i in range(n):
	heappush(heap, c[i])
	l[i] = max(l[i] - till, 0)
	while l[i] > 0 and heap:
		k = heappop(heap)
		cost += k
		l[i] -= 1
		till += 1
	if l[i] > 0:
		flag = False
		break
if flag:
	print(cost)
else:
	print(-1)


from heapq import *

def main():
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	req = list(map(lambda x: int(x), input().split()))
	each = int(input())
	prices = list(map(lambda x: int(x), input().split()))
	total = 0
	hp = []
	heapify(hp)
	for i in range(n):
		heappush(hp, prices[i])
		needed = (req[i] - k + each - 1) // each
		needed = max(0, needed)
		if len(hp) < needed:
			print(-1)
			return
		for j in range(needed):
			total += heappop(hp)
			k += each
	print(total)
main()


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
d = int(input())
c = list(map(int, input().split()))
ans = 0
temp = []
for i in range(n):
	temp.append(c[i])
	temp.sort()
	if p < a[i]:
		for j in range(0, len(temp)):
			p += d
			ans += temp.pop(0)
			if p >= a[i]:
				break
	if p < a[i]:
		ans = -1
		break
print(ans)


from sys import stdin
from heapq import heappop, heappush

def main():
	(n, k) = map(int, stdin.readline().split())
	X = list(map(int, stdin.readline().split()))
	A = int(stdin.readline().strip())
	C = list(map(int, stdin.readline().split()))
	l = list()
	i = 0
	g = k
	ans = 0
	flag = True
	while i < n and flag:
		heappush(l, C[i])
		if X[i] > g:
			while len(l) != 0 and X[i] > g:
				ans += heappop(l)
				g += A
			if len(l) == 0 and X[i] > g:
				flag = False
		i += 1
	if flag:
		print(ans)
	else:
		print(-1)
main()


import sys
input = sys.stdin.readline
import collections
from heapq import *

def minCost(w, t, weights, costs):
	heap = []
	tot = 0
	for (weight, cost) in zip(weights, costs):
		heappush(heap, cost)
		while w < weight and heap:
			w += t
			tot += heappop(heap)
		if w < weight:
			return -1
	return tot

def main():
	(n, w) = input().split()
	(n, w) = (int(n), int(w))
	tmp = input().split()
	weights = [int(x) for x in tmp]
	t = int(input())
	tmp = input().split()
	costs = [int(x) for x in tmp]
	print(minCost(w, t, weights, costs))
main()


import heapq
(n, k) = map(int, input().split())
lis = list(map(int, input().split()))
energy = int(input())
cost = list(map(int, input().split()))
h = []
length = len(lis)
output = 0
for i in range(length):
	heapq.heappush(h, cost[i])
	if lis[i] > k:
		while h:
			if k >= lis[i]:
				break
			output += heapq.heappop(h)
			k += energy
		if k < lis[i]:
			print(-1)
			break
else:
	print(output)


import heapq as hp
import sys
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
p = int(input())
arrx = list(map(int, input().split()))
prev = []
hp.heapify(prev)
cost = 0
flag = 0
for i in range(n):
	hp.heappush(prev, arrx[i])
	while arr[i] > k and len(prev) > 0:
		k += p
		cost += hp.heappop(prev)
	if k < arr[i]:
		flag = 1
		break
if flag == 1:
	print(-1)
else:
	print(cost)


import heapq
(n, k) = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
a = int(input())
c = list(map(int, input().split(' ')))
(pq, ans) = ([], 0)
for i in range(n):
	heapq.heappush(pq, c[i])
	while x[i] > k and len(pq) > 0:
		k += a
		ans += heapq.heappop(pq)
	if k < x[i]:
		print('-1')
		return
print(ans)


import heapq
(n, k) = map(int, input().split())
x = list(map(int, input().split()))
a = int(input())
c = list(map(int, input().split()))
m = 0
f = 1
temp = []
heapq.heapify(temp)
for i in range(n):
	heapq.heappush(temp, c[i])
	if x[i] > k:
		while k < x[i]:
			if len(temp) != 0:
				k += a
				temp2 = heapq.heappop(temp)
				m += temp2
			else:
				print(-1)
				f = 0
				break
	if f == 0:
		break
if f == 1:
	print(m)