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.

Difficulty: competition

Starter code:

Solutions:
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()

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])
        #print(f"day{i}, max{k}")
        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()

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)

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 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 sys
from queue import PriorityQueue

n, k = (list(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()



            # print(m_q)
                k = k + a
                if k>=t[j]:

                    break





            #print(cost, j)


        else:

            m_q.put(c[j])
    print(cost)


import heapq
import sys
n,k=list(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):
        #print(l)
        b=(arr[i]-l-1)//add + 1
        if size<b:
            print(-1)
            return
        else:
            if b==0:
                break
            for j in range(b):
                ans+=heapq.heappop(s)
                l+=add
                #print(ans)
                size-=1
            #print("helo")
print(ans)
            


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 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()

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):
        if x > k:
            while x > k:
                s = min(cs[:i+1-j])
                cs.remove(s)
                r += s
                j += 1
                k += a
            if x > k:
                raise
except:
    print(-1)
    quit()
print(r)

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 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)

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
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(" ")))
    #drunk = [0]*N
    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()
    


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


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 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)

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)



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 
n,initial=list(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)