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: HARD
Tags: Sorting

Mathematics
Skill types: Sorting

Starter code:

Solutions:
(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 = 1e+16
	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()))
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) = map(int, input().split())
if c <= a:
	print(0)
	exit()
(l, r) = (0, (c - a) * int(10000.0))
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)


__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 sys

def solve():
	(a, b, w, x, c) = map(int, input().split())
	w -= x
	(small, large) = (0, int(1e+20))
	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())


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)


(a, b, w, x, c) = 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
	while c > a:
		c -= 1
		if b >= x:
			b = b - x
		else:
			a -= 1
			b = w - (x - b)
		poc += 1
	print(poc)


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