Arthur and Alexander are number busters. Today they've got a competition. 

Arthur took a group of four integers a, b, w, x (0 ≤ b < w, 0 < x < w) and Alexander took integer с. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: c = c - 1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if b ≥ x, perform the assignment b = b - x, if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b).

You've got numbers a, b, w, x, c. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if c ≤ a.


-----Input-----

The first line contains integers a, b, w, x, c (1 ≤ a ≤ 2·10^9, 1 ≤ w ≤ 1000, 0 ≤ b < w, 0 < x < w, 1 ≤ c ≤ 2·10^9).


-----Output-----

Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem's limits.


-----Examples-----
Input
4 2 3 1 6

Output
2

Input
4 2 3 1 7

Output
4

Input
1 2 3 2 6

Output
13

Input
1 1 2 1 1

Output
0

Difficulty: interview

Starter code:

Solutions:
a,b,w,x,c=list(map(int,input().split()))
ans=0
bb=b
benefit=0
Visited=[False]*1003
CycleCost=-1
while(1):
    if(c<=a):
        break
    if(Visited[b]!=False):
        CycleCost=ans-Visited[b][1]
        CycleBenefit=benefit-Visited[b][0]
        CycleBegining=b
        break
    Visited[b]=(benefit,ans)
    if(b<x):
        b=w-(x-b)
        ans+=1
    elif(b>=x):
        b-=x
        ans+=1
        benefit+=1
    if(benefit==c-a):
        break

if(CycleCost==-1):
    print(ans)
else:
    c-=benefit
    diff=c-a
    xx=diff//CycleBenefit
    if(xx!=0):
        xx-=1
        ans+=xx*CycleCost
        diff-=xx*CycleBenefit
    b=CycleBegining
    while(diff>0):
        if(b<x):
            b=w-(x-b)
            ans+=1
        else:
            b-=x
            ans+=1
            diff-=1
    print(ans)
        


a,b,w,x,c = list(map(int,input().split()))
poc = 0
s = set()
s.add(b)
pa,pb,pc = a,b,c
while (c > a) :
	c -= 1
	if b >= x:
		b = b-x
	else:
		a -= 1
		b = w - (x-b)
	if b in s:
		kolko = len(s)
		break
	s.add(b)
dl = len(s)
kolko = max(pa-a,1)
if dl == kolko:
	print(0)
else:
	roz = (pc-pa)//(dl-kolko) - 1
	poc = roz*dl
	c = pc - poc
	a = pa - roz*kolko
	b = pb
	#a,b,c,poc=pa,pb,pc,0
	#print(a,b,w,x,c)
	while (c > a) :
		c -= 1
		if b >= x:
			b = b-x
		else:
			a -= 1
			b = w - (x-b)
		poc+=1
		#print(a,b,w,x,c)
	print(poc)


__author__ = 'asmn'
a, b, w, x, c = tuple(map(int, input().split()))

if c <= a:
    print(0)
    return
l, r = 0, (c - a) * 10000
while l + 1 < r:
    m = (l + r) // 2

    if c - m <= a - (w - b - 1 + m * x) // w:
        r = m
    else:
        l = m
print(r)

import fileinput;

str = input();
sstr = str.split(' ')
a,b,w,x,c = int(sstr[0]),int(sstr[1]),int(sstr[2]),int(sstr[3]),int(sstr[4])

dif = c-a

up = max(0,int((dif*x-b)/(w-x)))
b = b+up*(w-x)

count = up
while dif > 0:
    if (b >= x):
        factor = min(int((b - x)/x)+1,dif)
        dif = dif-factor
        b = b - x*factor
    else:
        factor = int( (x-b-1)/(w-x) )+1
        b = factor*(w-x)+b
        count = count+factor

print(count+(c-a))


def f(t, c, b, w):
    a = b
    s = l = 0
    while True:
        b += w
        dt = b // x
        b -= dt * x
        s += dt
        l += 1
        if a == b: break
    k = c // s
    if c == k * s: k -= 1
    c -= k * s
    t += k * (s + l)
    while True:
        b += w
        dt = b // x
        b -= dt * x
        if c <= dt: return t + c
        c -= dt
        t += dt + 1

a, b, w, x, c = map(int, input().split())
t = b // x
if a >= c - t: print(c - min(c, a))
else: print(f(t + 1, c - t - a, b - t * x, w - x))

import sys
a, b, w, x, c = map(int, input().split())
if c <= a:
    print(0)
    return
d = c - a
ans = 0
if b // x >= d:
    print(d)
    return
ans += (b // x + 1) 
d -= (b // x)
b = w - (x - b % x)
b0 = b
g = 0
det = 0
while (1):
    if b // x >= d:
        print(ans + d)
        return
    g += (b // x + 1)
    det += (b // x)
    ans += (b // x + 1)
    d -= (b // x)
    b = w - (x - b % x)
    if b == b0:
        break

if d > det:
    k = d // det
    if (d % det == 0):
        k -= 1
    d -= det * k
    ans += k * g
while (1):
    if b // x >= d:
        print(ans + d)
        return
    ans += (b // x + 1)
    d -= (b // x)
    b = w - (x - b % x)

import sys

def solve():
    a, b, w, x, c = map(int, input().split())
    w -= x
    small, large = 0, int(1e20)
    while small < large:
        avg = (small + large) // 2
        if works(avg, a, b, c, w, x): large = avg
        else: small = avg + 1
    return small

def works(val, a, b, c, w, x):
    cres = c - val
    amin = cres
    maxsubtract = a - amin
    if maxsubtract < 0: return False
    bsubtract = val - maxsubtract
    bres = b + maxsubtract * w - x * bsubtract
    return bres >= 0
    
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
print(solve())

a, b, w, x, c = map(int, input().split())

def result(a, b, w, x, c, s):
	na = a - (s * x - b) / w
	nc = c - s
	return (na, nc)

def solve(a, b, w, x, c):
	left = 0
	right = 10e15
	if (c <= a):
		return 0

	while (left < right):
		half = (left+right) // 2
		ret = result(a, b, w, x, c, half)
		if (ret[1] <= ret[0]):
			right = half
		else:
			left = half + 1

	return left

print(int(solve(a, b, w, x, c)))

a, b, w, x, c = list(map(int, input().split()))



def result(a, b, w, x, c, s):

	na = a - (s * x - b) / w

	nc = c - s

	return (na, nc)



def solve(a, b, w, x, c):

	left = 0

	right = 10e15

	if (c <= a):

		return 0



	while (left < right):

		half = (left+right) // 2

		ret = result(a, b, w, x, c, half)

		if (ret[1] <= ret[0]):

			right = half

		else:

			left = half + 1



	return left



print(int(solve(a, b, w, x, c)))



# Made By Mostafa_Khaled


a, b, w, x, c = list(map(int, input().split()))
if c <= a:
    print(0)
    return
l, r = 0, (c - a) * int(1e4)
while l + 1 < r:
    m = (l + r) // 2
    if c - m <= a - (w - b - 1 + m * x) // w: 
        r = m
    else: 
        l = m
print(r)