Valera loves his garden, where n fruit trees grow.

This year he will enjoy a great harvest! On the i-th tree b_{i} fruit grow, they will ripen on a day number a_{i}. Unfortunately, the fruit on the tree get withered, so they can only be collected on day a_{i} and day a_{i} + 1 (all fruits that are not collected in these two days, become unfit to eat).

Valera is not very fast, but there are some positive points. Valera is ready to work every day. In one day, Valera can collect no more than v fruits. The fruits may be either from the same tree, or from different ones. What is the maximum amount of fruit Valera can collect for all time, if he operates optimally well?


-----Input-----

The first line contains two space-separated integers n and v (1 ≤ n, v ≤ 3000) — the number of fruit trees in the garden and the number of fruits that Valera can collect in a day. 

Next n lines contain the description of trees in the garden. The i-th line contains two space-separated integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 3000) — the day the fruits ripen on the i-th tree and the number of fruits on the i-th tree.


-----Output-----

Print a single integer — the maximum number of fruit that Valera can collect. 


-----Examples-----
Input
2 3
1 5
2 3

Output
8

Input
5 10
3 20
2 20
1 20
4 20
5 20

Output
60



-----Note-----

In the first sample, in order to obtain the optimal answer, you should act as follows.   On the first day collect 3 fruits from the 1-st tree.  On the second day collect 1 fruit from the 2-nd tree and 2 fruits from the 1-st tree.  On the third day collect the remaining fruits from the 2-nd tree.  

In the second sample, you can only collect 60 fruits, the remaining fruit will simply wither.

Difficulty: MEDIUM
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, v) = map(int, input().split(' '))
trees = dict()
count = 0
b_last = 0
for i in range(n):
	(a, b) = map(int, input().split(' '))
	if trees.get(a):
		trees[a] += b
	else:
		trees[a] = b
m = max(trees.keys())
for i in range(1, m + 2):
	if trees.get(i):
		k = min(v, b_last)
		count += k
		k1 = min(v - k, trees[i])
		count += k1
		b_last = trees[i] - k1
	else:
		count += min(v, b_last)
		b_last = 0
print(count)


(n, v) = map(int, input().split())
d = [0] * 3001
for _ in range(n):
	(a, b) = map(int, input().split())
	d[a - 1] += b
sum = min(v, d[0])
d[0] = max(0, d[0] - v)
for i in range(1, 3001):
	sum += min(v, d[i - 1] + d[i])
	d[i] = max(0, d[i] - max(0, v - d[i - 1]))
print(sum)


[n, v] = input().split()
v1 = []
for i in range(3002):
	v1.append(0)
v = int(v)
maxx = 0
for i in range(int(n)):
	[a, b] = input().split()
	v1[int(a)] += int(b)
	maxx = max(int(a), maxx)
res = 0
for i in range(1, maxx + 2):
	delt = min(v, v1[i] + v1[i - 1])
	res += delt
	d = v1[i - 1] - delt
	v1[i] += min(d, 0)
print(res)


(n, v) = map(int, input().split())
N = 3003
t = [0] * N
for i in range(n):
	(a, b) = map(int, input().split())
	t[a] += b
res = 0
for i in range(1, N):
	c = v
	res += min(c, max(t[i - 1], 0))
	c -= max(t[i - 1], 0)
	if c > 0:
		res += min(c, t[i])
		t[i] = max(t[i] - c, 0)
print(res)


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def main():
	try:
		(n, v) = invr()
		a = [0] * 3002
		for i in range(n):
			(x, y) = invr()
			a[x] += y
		ans = 0
		prev = 0
		for i in range(1, 3002):
			curr = a[i]
			if curr + prev <= v:
				ans += curr + prev
				curr = 0
			else:
				ans += v
				if prev < v:
					curr -= v - prev
			prev = curr
		print(ans)
	except Exception as e:
		print(e)
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 gcd

def take_input(s):
	if s == 1:
		return int(input())
	return map(int, input().split())
(n, v) = take_input(2)
d = {0: 0}
days = 1
for i in range(n):
	(ai, bi) = take_input(2)
	d[ai] = d.get(ai, 0) + bi
	if ai > days:
		days = ai
ans = 0
prev_day = 0
for i in range(1, days + 2):
	day_lim = min(d.get(i - 1, 0), v)
	d[i - 1] = d.get(i - 1, 0) - day_lim
	ans += day_lim
	if day_lim < v:
		prev_c = min(v - day_lim, d.get(i, 0))
		d[i] = d.get(i, 0) - prev_c
		ans += prev_c
print(ans)


DEBUG = False
(n, v) = [int(x) for x in input().split()]
fruits = []
for i in range(n):
	(aa, bb) = [int(x) for x in input().split()]
	fruits.append([aa, bb])
fruits.sort()
(day, t_harvested, tot, curr) = (0, 0, 0, [])

def remove_old():
	while fruits != [] and fruits[0][0] < day - 1:
		t = fruits.pop(0)
		if DEBUG:
			print('Rotten {} on day {}'.format(t, day))
	while curr != [] and curr[0][0] < day - 1:
		curr.pop(0)

def add_current():
	for f in fruits:
		if day - 1 <= f[0] <= day:
			curr.append(f)
			if DEBUG:
				print('New fruit {} on day {}'.format(f, day))

def harvest_todays():
	global t_harvested
	global tot
	while curr != []:
		t = curr.pop(0)
		harvest = min(t[1], v - t_harvested)
		if DEBUG:
			print('Harvested {} of {} on day {}'.format(harvest, t, day))
		t_harvested += harvest
		t[1] -= harvest
		tot += harvest
while fruits != []:
	remove_old()
	add_current()
	harvest_todays()
	day += 1
	t_harvested = 0
print(tot)


(n, v) = map(int, input().split())
g = [0 for x in range(3002)]
for i in range(n):
	(a, b) = map(int, input().split())
	g[a] += b
r = 0
for i in range(1, 3002):
	c = v
	r += min(c, max(g[i - 1], 0))
	c -= max(g[i - 1], 0)
	if c > 0:
		r += min(c, g[i])
		g[i] = max(g[i] - c, 0)
print(r)


(n, V) = map(int, input().split())
A = []
max_no_of_days = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	A.append([a, b])
	max_no_of_days = max(max_no_of_days, a)
A.sort()
Fruits = [0] * (max_no_of_days + 2)
for i in A:
	Fruits[i[0]] += i[1]
S = 0
for i in range(1, max_no_of_days + 2):
	v = V
	if Fruits[i - 1]:
		y = min(Fruits[i - 1], v)
		S += y
		v -= y
	x = min(Fruits[i], v)
	S += x
	v -= x
	Fruits[i] -= x
print(S)


frukti_po_dnyam = {}
(n, resurs) = map(int, input().split(' '))
for i in range(n):
	(den, chislo_fruktov) = map(int, input().split(' '))
	if den in frukti_po_dnyam:
		frukti_po_dnyam[den] += chislo_fruktov
	else:
		frukti_po_dnyam[den] = chislo_fruktov
	if den + 1 not in frukti_po_dnyam:
		frukti_po_dnyam[den + 1] = 0

def ubir(chislo, vichet):
	tmp = chislo - vichet
	if tmp < 0:
		return (0, -tmp)
	return (tmp, 0)
vsego = 0
for i in sorted(frukti_po_dnyam):
	ostatok = resurs
	if i - 1 in frukti_po_dnyam:
		(frukti_po_dnyam[i - 1], ostatok) = ubir(frukti_po_dnyam[i - 1], ostatok)
	(frukti_po_dnyam[i], ostatok) = ubir(frukti_po_dnyam[i], ostatok)
	vsego += resurs - ostatok
print(vsego)


def main():
	R = lambda : map(int, input().split())
	(n, v) = R()
	mlist = [0] * 3003
	for i in range(n):
		(a, b) = R()
		mlist[a] += b
	mlist2 = mlist[:]
	ans = 0
	for i in range(1, 3002):
		tmp = min(v, mlist[i])
		ans += tmp
		mlist[i + 1] += min(mlist[i] - tmp, mlist2[i])
	print(ans)
main()


(n, v) = map(int, input().split())
lis = [0] * 4000
for i in range(n):
	(a, b) = map(int, input().split())
	lis[a] += b
prev = 0
ans = 0
for i in range(1, 4000):
	cap = v
	cap = v - min(prev, v)
	ans += min(prev, v)
	zz = min(lis[i], cap)
	ans += zz
	prev = lis[i] - zz
print(ans)


import sys
f = sys.stdin
(n, v) = map(int, f.readline().strip().split())
p = [0] * 3002
for i in range(n):
	(a, b) = map(int, f.readline().strip().split())
	p[a] += b
S = 0
for k in range(1, len(p)):
	dv = min(v, p[k - 1])
	S += dv
	p[k - 1] -= dv
	dv = min(v - dv, p[k])
	S += dv
	p[k] -= dv
print(S)


(n, v) = map(int, input().split())
a = [0] * 3002
ans = 0
for i in range(n):
	(y, x) = map(int, input().split())
	a[y] += x
for i in range(1, 3002):
	usable = v
	z = min(usable, a[i - 1])
	ans += z
	usable -= z
	a[i - 1] -= z
	z = min(usable, a[i])
	ans += z
	usable -= z
	a[i] -= z
print(ans)


(n, v) = map(int, input().split())
arr = [0] * 3002
for _ in range(n):
	(a, b) = map(int, input().split())
	arr[a] += b
x = v
ans = 0
prev = 0
for i in range(1, 3002):
	x = max(x - prev, 0)
	ans += v - x
	if arr[i] <= x:
		ans += arr[i]
		prev = 0
	else:
		ans += x
		prev = arr[i] - x
	x = v
print(ans)


(n, v) = map(int, input().split())
trees = [0] * 3002
for i in range(n):
	(a, b) = map(int, input().split())
	trees[a] += b
ans = 0
prev = 0
for i in range(1, len(trees)):
	available = min(v, prev + trees[i])
	ans += available
	if prev >= v:
		prev = trees[i]
	else:
		prev = max(0, trees[i] - (v - prev))
print(ans)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
import heapq
(n, m) = mp()
mx = 30002
v = [0] * mx
for _ in range(n):
	l = mp()
	v[l[0]] += l[1]
ans = 0
prev = 0
for i in range(1, mx):
	if prev + v[i] <= m:
		ans += prev + v[i]
		prev = 0
	else:
		ans += m
		prev = max(0, v[i] - max(0, m - prev))
print(ans)


(n, k) = map(int, input().split())
c = 0
l = [0] * 3005
for i in range(n):
	(a, b) = map(int, input().split())
	l[a] += b
ans = 0
for i in range(1, 3002):
	if l[i] + c >= k:
		ans += k
		if c > k:
			c = l[i]
		else:
			c = l[i] - (k - c)
	else:
		ans += l[i] + c
		c = 0
ans += min(c, k)
print(ans)


(n, v) = [int(c) for c in input().split()]
m = [[0, 0] for i in range(3003)]
for i in range(n):
	(a, b) = [int(c) for c in input().split()]
	m[a][1] += b
	m[a + 1][0] += b
res = 0
for i in range(1, 3002):
	if v <= m[i][0]:
		res += v
	else:
		from_future = v - m[i][0]
		got_fr = min(from_future, m[i][1])
		res += m[i][0] + got_fr
		m[i + 1][0] -= got_fr
print(res)


(n, v) = map(int, input().split())
d = {}
for i in range(n):
	(a, b) = map(int, input().split())
	if a in d:
		d[a] += b
	else:
		d[a] = b
mi = min(d.keys())
ma = max(d.keys())
c = 0
for i in range(mi, ma + 3):
	quota = v
	if i - 1 in d:
		if quota > d[i - 1]:
			c += d[i - 1]
			quota -= d[i - 1]
			d[i - 1] = 0
		else:
			c += quota
			d[i - 1] -= quota
			quota = 0
	if i in d:
		if quota > d[i]:
			c += d[i]
			quota -= d[i]
			d[i] = 0
		else:
			c += quota
			d[i] -= quota
			quota = 0
print(c)


(n, v) = [int(i) for i in input().split()]
f = 0
l = [0] * 3002
for i in range(n):
	(a, b) = [int(i) for i in input().split()]
	l[a] += b
for i in range(1, 3002):
	pick = min(v, l[i - 1])
	l[i - 1] -= pick
	pick2 = min(v - pick, l[i])
	l[i] -= pick2
	f += pick + pick2
print(f)


(n, v) = [int(i) for i in input().split()]
d = {}
for i in range(n):
	(a, b) = [int(i) for i in input().split()]
	if a in d:
		d[a] += b
	else:
		d[a] = b
set_tree = sorted(d)
set_tree = list(range(1, max(set_tree) + 2))
set_tree.append(0)
d[0] = 0
S = 0
for i in set_tree:
	if i in d:
		None
	else:
		d[i] = 0
for i in set_tree[:-1]:
	if d[i] <= v:
		S += d[i]
	elif d[i] >= 2 * v:
		S += v
		d[i + 1] = d[i + 1] + v
	else:
		S += v
		d[i + 1] += d[i] - v
print(S)


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
import heapq
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'
mod = 10 ** 9 + 7

def ii():
	return int(I().strip())

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

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def ispali(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	(n, v) = mi()
	arr = [0] * 3002
	for i in range(n):
		(a, b) = mi()
		arr[a] += b
	ans = 0
	for i in range(1, 3002):
		cantake = v
		x = min(cantake, arr[i - 1])
		cantake -= x
		ans += x
		x = min(cantake, arr[i])
		ans += x
		arr[i] -= x
	print(ans)
main()


import sys
input = sys.stdin.readline

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)
import math

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

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

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right
import heapq
import math

def divisors_seive(n):
	divisors = [10 ** 6 + 6]
	for i in range(1, n + 1):
		for j in range(i, n + 1):
			divisors[j] += 1

def dfs(s, par, vis, rank):
	vis[s] = 1
	global res
	res = 1
	rank[s] = 1
	f = 0
	for i in g[s]:
		f = 1
		if par == i:
			continue
		rank[s] += dfs(i, s)
	return res
import bisect
from collections import deque
(n, v) = map(int, input().split())
arr = []
for i in range(n):
	(x, y) = map(int, input().split())
	arr.append([x, y])
arr = sorted(arr, key=lambda x: (x[0], x[1]))
day = 1
ans = 0
f = 0
while arr:
	limit = v
	while arr[0][0] < day - 1:
		arr = arr[1:]
		if arr == []:
			f = 1
			break
	if f == 1 or arr == []:
		break
	if arr[0][0] == day or arr[0][0] == day - 1:
		var = arr[0][1]
		if var > limit:
			arr[0][1] -= limit
			ans += limit
		else:
			ans += var
			arr = arr[1:]
			limit -= var
			if arr:
				while limit > 0 and arr[0][0] == day or arr[0][0] == day - 1:
					if arr[0][1] < limit:
						limit -= arr[0][1]
						ans += arr[0][1]
						arr = arr[1:]
					else:
						ans += limit
						arr[0][1] -= limit
						break
					if arr == []:
						break
	day += 1
print(ans)


(n, v) = [int(x) for x in input().split(' ')]
a_dict = {}
m = 0
p = 0
for tree in range(n):
	(a, b) = [int(x) for x in input().split(' ')]
	m = max(a, m)
	if a in a_dict.keys():
		a_dict[a] += b
	else:
		a_dict[a] = b
for day in range(m + 2):
	if day not in a_dict.keys():
		a_dict[day] = 0
for day in range(1, m + 2):
	y = min(v, a_dict[day - 1])
	a_dict[day - 1] -= y
	z = min(v - y, a_dict[day])
	a_dict[day] -= z
	p += z + y
print(p)


(n, v) = map(int, input().split())
T = 3010
a = [[] for i in range(T)]
for i in range(n):
	(x, y) = map(int, input().split())
	a[x].append([y, 1])
ans = 0
for i in range(T):
	a[i] = a[i][::-1]
	j = 0
	cur = v
	while j < len(a[i]):
		if a[i][j][0] > cur:
			ans += cur
			if a[i][j][1] == 0:
				j += 1
			else:
				a[i][j][0] -= cur
			break
		else:
			ans += a[i][j][0]
			cur -= a[i][j][0]
		j += 1
	for t in range(j, len(a[i])):
		if a[i][t][1] != 0:
			a[i + 1].append([a[i][t][0], 0])
print(ans)


def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return [int(x) for x in inputs.split()]

def write(s='\n'):
	if isinstance(s, list):
		s = ' '.join(s)
	s = str(s)
	print(s, end='')
(n, v) = read()
a = []
for i in range(n):
	a.append(read())
a.sort(key=lambda x: x[0])
res = 0
for day in range(1, 3002):
	n = 0
	while a and a[0][0] <= day:
		if a[0][1] <= v - n:
			n += a[0][1]
			a[0][1] = 0
		else:
			a[0][1] -= v - n
			n = v
		if a[0][1] == 0:
			a.pop(0)
		else:
			break
	while a and a[0][0] == day - 1:
		a.pop(0)
	res += n
print(res)


(n, v) = list(map(int, input().split()))
trees = {}
days = set()
for i in range(n):
	(a, b) = list(map(int, input().split()))
	if a not in trees:
		trees[a] = b
	else:
		trees[a] += b
	days.add(a)
max_days = max(days)
total = 0
for a in range(1, max_days + 1):
	prev_collected = 0
	if a - 1 in trees:
		prev_collected = min(trees[a - 1], v)
		trees[a - 1] -= prev_collected
		total += prev_collected
	if a in trees:
		collected = min(trees[a], v - prev_collected)
		trees[a] -= collected
		total += collected
	elif a - 1 in trees and prev_collected == 0:
		add_collected = min(trees[a - 1], v)
		trees[a - 1] -= add_collected
		total += add_collected
if max_days in trees:
	total += min(trees[max_days], v)
print(total)


(n, v) = map(int, input().split())
f = [0] * 3002
for _ in range(n):
	(a, b) = map(int, input().split())
	f[a] += b
ans = 0
cur = 0
for i in range(1, 3002):
	if cur + f[i] <= v:
		ans += cur + f[i]
		cur = 0
	else:
		ans += v
		cur = f[i] - max(v - cur, 0)
print(ans)


def main():
	(n, v) = map(int, input().split())
	l = [0] * 3002
	for _ in range(n):
		(a, b) = map(int, input().split())
		l[a] += b
	a = res = 0
	for b in l:
		x = a + b
		if x < v:
			res += x
			a = 0
		else:
			res += v
			if a < v:
				a = x - v
			else:
				a = b
	print(res)
main()


(total, limit) = map(int, input().split())
l = [int(0)] * 3002
due = [int(0)] * 3002
ans = int(0)
for i in range(total):
	(day, mango) = map(int, input().split())
	l[day - 1] += mango
for i in range(3002):
	tut = limit
	if due[i] <= tut:
		ans += due[i]
		tut -= due[i]
	else:
		ans += tut
		tut = 0
	if l[i] <= tut:
		ans += l[i]
		tut -= l[i]
	else:
		ans += tut
		due[i + 1] = l[i] - tut
print(ans)


(n, v) = map(int, input().split(' '))
(a, b) = ([], [])
for i in range(n):
	(x, y) = map(int, input().split(' '))
	a.append(x)
	b.append(y)
fi = max(a)
li = []
for i in range(fi + 3):
	li.append([0, 0])
for i in range(n):
	li[a[i]][1] += b[i]
ans = 0
for i in range(fi + 2):
	if li[i][0] <= v:
		ans += li[i][0]
		if li[i][1] <= v - li[i][0]:
			ans += li[i][1]
		else:
			ans += v - li[i][0]
			li[i + 1][0] = li[i][1] - v + li[i][0]
	else:
		ans += v
		li[i + 1][0] = li[i][1]
print(ans)


(n, v) = map(int, input().split())
lst = [0] * 4001
for _ in range(n):
	(a, b) = map(int, input().split())
	lst[a] += b
b = lst[:]
t = 0
for day in range(4000):
	x = min(v, b[day])
	t += x
	b[day + 1] += min(b[day] - x, lst[day])
print(t)


from io import BytesIO, IOBase
from math import sqrt
import sys, os
inpl = lambda : list(map(int, input().split()))
inpm = lambda : map(int, input().split())
inpi = lambda : int(input())
inp = lambda : input()
(rev, ra, l) = (reversed, range, len)
P = print
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def B(n):
	return bin(n).replace('0b', '')

def factors(n):
	arr = []
	for i in ra(2, int(sqrt(n)) + 1):
		if n % i == 0:
			arr.append(i)
			if i * i != n:
				arr.append(int(n / i))
	return arr

def dfs(arr, n):
	pairs = [[i + 1] for i in ra(n)]
	vis = [0] * (n + 1)
	for i in ra(l(arr)):
		pairs[arr[i][0] - 1].append(arr[i][1])
	pairs[arr[i][1] - 1].append(arr[i][0])
	comp = []
	for i in ra(n):
		stack = [pairs[i]]
		temp = []
		if vis[stack[-1][0]] == 0:
			while len(stack) > 0:
				if vis[stack[-1][0]] == 0:
					temp.append(stack[-1][0])
					vis[stack[-1][0]] = 1
					s = stack.pop()
					for j in s[1:]:
						if vis[j] == 0:
							stack.append(pairs[j - 1])
				else:
					stack.pop()
			comp.append(temp)
	return comp
from bisect import bisect_left as bl
from bisect import bisect_right as br
import sys, operator, math, operator
from collections import Counter
import random
(n, x) = inpm()
li = []
for i in ra(n):
	li.append(inpl())
omap = {}
for i in ra(3002):
	omap[i] = 0
li.sort(reverse=True)
for i in ra(n):
	omap[li[i][0]] += li[i][1]
ma = li[0][0]
ans = 0
for i in ra(1, ma + 2):
	take = min(omap[i - 1], x)
	rem = x - take
	ans += take
	take1 = min(rem, omap[i])
	ans += take1
	omap[i] -= take1
P(ans)


def main():
	(n, m) = map(int, input().split())
	a = []
	b = []
	for _ in range(n):
		(a1, b1) = map(int, input().split())
		a.append(a1)
		b.append(b1)
	prev = 0
	tv = 0
	ans = 0
	for i in range(1, 3002):
		curr = 0
		for j in range(n):
			if a[j] == i:
				curr += b[j]
		if curr + prev <= m:
			ans += prev + curr
			prev = 0
		else:
			ans += m
			tv = m - prev
			if tv < 0:
				tv = 0
			prev = curr - tv
	print(ans)
	return
main()


read = lambda : map(int, input().split())
(n, v) = read()
N = 3002
p = [0] * N
for i in range(n):
	(a, b) = read()
	p[a] += b
ans = 0
rem = 0
for i in range(1, N):
	cur = min(v, rem + p[i])
	ans += cur
	if rem >= v:
		rem = p[i]
	else:
		rem = max(0, p[i] - (v - rem))
print(ans)


import collections

def main():
	hash_sum = collections.defaultdict(int)
	sum = 0
	(n, v) = map(int, input().split())
	for i in range(n):
		(a, b) = map(int, input().split())
		hash_sum[a] += b
	for i in range(1, 3002):
		current = hash_sum[i]
		prev = hash_sum[i - 1]
		taken = min(v, prev)
		hash_sum[i - 1] -= taken
		sum += taken
		taken = min(v - taken, current)
		hash_sum[i] -= taken
		sum += taken
	return sum
result = main()
print(result)


from sys import stdin, stdout
from math import gcd, ceil, sqrt
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
(n, v) = iia()
arr = []
for _ in range(n):
	arr.append(iia())
arr.sort()
res = day = remain = 0
for i in arr:
	if i[0] > day:
		day = i[0]
		res += min(i[1], v)
		remain = v - min(i[1], v)
		if i[1] > v:
			res += min(v, i[1] - v)
			remain = v - min(v, i[1] - v)
			day += 1
	elif i[0] == day:
		if remain >= i[1]:
			res += i[1]
			remain -= i[1]
		else:
			day += 1
			res += remain
			res += min(v, i[1] - remain)
			remain = v - min(v, i[1] - remain)
	elif i[0] + 1 == day:
		if i[1] >= remain:
			res += remain
			remain = 0
		else:
			res += i[1]
			remain -= i[1]
print(res)


(n, m) = map(int, input().split())
d = {}
for i in range(n):
	(a, b) = map(int, input().split())
	d[a] = d.get(a, 0) + b
d = {x: d[x] for x in sorted(d)}
p = -1
r = 0
out = 0
for x in d:
	if x - p > 1:
		r = 0
	p = x
	f = min(d[x], m * 2 - r)
	r = max(min(m, d[x] - m + r), 0)
	out += f
print(out)


T = 3333
(n, v) = map(int, input().split())
data = [0] * T
for i in range(0, n):
	(a, b) = map(int, input().split())
	data[a] += b
answer = 0
for i in range(1, T):
	x = v
	tmp = min(v, data[i - 1])
	x -= tmp
	data[i - 1] -= tmp
	answer += tmp
	tmp = min(x, data[i])
	data[i] -= tmp
	answer += tmp
print(answer)


(n, v) = map(int, input().split())
inp = []
for i in range(n):
	(x, y) = map(int, input().split())
	e = [x, y]
	inp.append(e)
inp = sorted(inp)
b = []
a = []
for e in inp:
	a.append(e[0])
	b.append(e[1])
cur = 0
day = 1
ans = 0
while day <= a[-1] + 1:
	while day > a[cur] + 1 and cur + 1 < len(a):
		cur += 1
	if day == a[cur] or day == a[cur] + 1:
		cap = v
		while cap > 0 and (day == a[cur] or day == a[cur] + 1):
			take = min(cap, b[cur])
			cap -= take
			b[cur] -= take
			ans += take
			if b[cur] == 0:
				if cur + 1 == len(a):
					break
				else:
					cur += 1
	day += 1
print(ans)


(n, v) = map(int, input().split())
w = []
q = [v for i in range(3003)]
for i in range(n):
	w.append(list(map(int, input().split())))
w = sorted(w, reverse=True)
s = 0
for i in w:
	a = i[0]
	b = i[1]
	if q[a + 1] >= b:
		q[a + 1] -= b
		s += b
		b = 0
	else:
		b -= q[a + 1]
		s += q[a + 1]
		q[a + 1] = 0
	if q[a] >= b:
		q[a] -= b
		s += b
		b = 0
	else:
		b -= q[a]
		s += q[a]
		q[a] = 0
print(s)


(n, v) = [int(i) for i in input().split()]
a = [0] * n
b = [0] * n
days1 = [0] * 3001
days2 = [0] * 3001
for i in range(n):
	(a[i], b[i]) = [int(j) for j in input().split()]
	days1[a[i] - 1] += b[i]
	days2[a[i]] += b[i]
res = 0
for i in range(3001):
	left = max(0, v - days2[i])
	res += max(0, min(v, days2[i]))
	res += min(left, days1[i])
	if i != 3000:
		days2[i + 1] -= min(left, days1[i])
print(res)


def a():
	(n, v) = list(map(int, input().split(' ')))
	d = []
	for i in range(n):
		d.append(list(map(int, input().split(' '))))
	d.sort()
	cur = 0
	nex = 0
	k = 0
	r = 0
	for i in range(d[-1][0] + 2):
		nex = 0
		p = v
		if k != n:
			while d[k][0] < i:
				k += 1
				if k == n:
					break
		if k != n:
			while d[k][0] == i:
				nex += d[k][1]
				k += 1
				if k == n:
					break
		r += min(p, cur)
		p -= min(p, cur)
		r += min(p, nex)
		cur = nex - min(p, nex)
	return r
print(a())


(n, v) = map(int, input().split())
l = [0] * 3010
ans = 0
for i in range(n):
	(a, b) = map(int, input().split())
	l[a] += b
day = 1
for i in range(3004):
	temp = min(v, l[day - 1])
	ans += temp
	l[day - 1] -= temp
	rem = v - temp
	temp2 = min(rem, l[day])
	ans += temp2
	l[day] -= temp2
	day += 1
print(ans)


(n, v) = map(int, input().split())
apples = [0] * 3002
for i in range(n):
	(a, b) = map(int, input().split())
	apples[a] += b
count = 0
for i in range(1, 3002):
	leftover = apples[i - 1]
	collectable = min(v, apples[i] + leftover)
	count += collectable
	apples[i] = apples[i] + min(0, leftover - collectable)
print(count)


(n, v) = map(int, input().split())
l = []
for i in range(n):
	l += [list(map(int, input().split()))]
l.sort()
r = [0] * (3000 + 2)
t = 0
for i in range(n):
	if r[l[i][0]] + l[i][1] <= v:
		r[l[i][0]] += l[i][1]
	elif r[l[i][0]] + r[l[i][0] + 1] + l[i][1] <= 2 * v:
		t = r[l[i][0]]
		r[l[i][0]] += v - r[l[i][0]]
		l[i][1] -= v - t
		r[l[i][0] + 1] += l[i][1]
	else:
		r[l[i][0]] = v
		r[l[i][0] + 1] = v
print(sum(r))


total_plucked = 0
(n, v) = list(map(int, input().split()))
fruits = [0] * 3002
plucked = [0] * 30002
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	fruits[a] = fruits[a] + b
for i in range(1, 3002):
	plucked[i] = fruits[i - 1] if fruits[i - 1] <= v else v
	if plucked[i] < v:
		pluck = fruits[i] if fruits[i] <= v - plucked[i] else v - plucked[i]
		plucked[i] += pluck
		fruits[i] -= pluck
	total_plucked += plucked[i]
print(total_plucked)


(n, v) = map(int, input().split())
trees = [list(map(int, input().split())) for i in range(n)]
trees.sort()
mergedTrees = []
treeIndex = 0
currentDay = trees[treeIndex][0]
while treeIndex < len(trees):
	nbFruits = 0
	while treeIndex < len(trees) and trees[treeIndex][0] == currentDay:
		nbFruits += trees[treeIndex][1]
		treeIndex += 1
	mergedTrees.append([currentDay, nbFruits])
	if treeIndex < len(trees):
		currentDay = trees[treeIndex][0]
collected = 0
for (treeIndex, tree) in enumerate(mergedTrees):
	used = 0
	if treeIndex >= 1:
		lastTree = mergedTrees[treeIndex - 1]
		if lastTree[0] == tree[0] - 1:
			used = min(v, lastTree[1])
		collected += min(v, lastTree[1])
	nextUsed = min(tree[1], v - used)
	collected += nextUsed
	tree[1] -= nextUsed
if len(mergedTrees) > 0:
	lastTree = mergedTrees[len(mergedTrees) - 1]
	collected += min(v, lastTree[1])
print(collected)


from math import *
b = input()
b = b.split()
n = int(b[0])
m = int(b[1])
a = []
for x in range(3010):
	a.append(0)
l = 0
for x in range(n):
	b = input()
	b = b.split()
	i = int(b[0])
	j = int(b[1])
	a[i] += j
	l = max(l, i)
sum = 0
s = m
cnt = 0
for x in a:
	if cnt > l + 1:
		break
	if x <= s:
		sum += x
		s = m
	else:
		sum += s
		v = x - s
		if a[cnt + 1] == 0:
			a[cnt + 1] = min(v, m)
			s = m
		else:
			sum += min(v, m)
			s = m - min(v, m)
	cnt += 1
print(sum)


(n, v) = map(int, input().split())
b = [0] * 3002
for _ in range(n):
	a = list(map(int, input().split()))
	b[a[0]] += a[1]
s = 0
for i in range(1, 3002):
	r = v
	t = min(r, b[i - 1])
	s += t
	r -= t
	b[i - 1] -= t
	t = min(r, b[i])
	s += t
	r -= t
	b[i] -= t
print(s)


(n, v) = map(int, input().split(' '))
(a, b) = ([], [])
for i in range(n):
	(x, y) = map(int, input().split(' '))
	a.append(x)
	b.append(y)
fi = max(a)
li = [0] * 3002
for i in range(n):
	li[a[i]] += b[i]
ans = 0
for i in range(1, 3002):
	ans += min(v, li[i - 1] + li[i])
	li[i] = max(0, li[i] - max(0, v - li[i - 1]))
print(ans)


(n, v) = map(int, input().split())
f = list()
for i in range(n):
	f.append(list(map(int, input().split())))
f.sort()
sum = 0
today = 0
tomor = 0
day = 0
rest = 0
for tree in f:
	if tree[0] > day + 1:
		sum += min(tomor, v)
		tomor = tree[1]
		sum += min(tomor, v)
		rest = v - min(tomor, v)
		tomor -= min(tomor, v)
		day = tree[0]
	elif tree[0] == day + 1:
		sum += min(tomor, v)
		rest = v - min(tomor, v)
		tomor = tree[1]
		t = min(tomor, rest)
		sum += t
		rest -= t
		tomor -= t
		day = tree[0]
	else:
		tomor += tree[1]
		t = min(tomor, rest)
		sum += t
		rest -= t
		tomor -= t
sum += min(tomor, v)
print(sum)


(n, m) = map(int, input().split())
lis = [0] * 3002
for i in range(n):
	(a, b) = map(int, input().split())
	lis[a] += b
ans = lef = 0
for i in range(1, 3002):
	ans += lef
	q = max(0, m - lef)
	ans += min(q, lis[i])
	lef = min(m, lis[i] - min(q, lis[i]))
print(ans)


R = lambda : list(map(int, input().split()))
(n, v) = R()
M = 3005
x = [0] * M
for i in range(n):
	(a, b) = R()
	x[a - 1] += b
y = [0] * M
s = 0
for i in range(M):
	a = min(v, y[i])
	b = min(v - a, x[i])
	s += a + b
	if i < M - 1:
		y[i + 1] = x[i] - b
print(s)


(n, v) = map(int, input().split())
l = []
for j in range(3001):
	l += [0]
for k in range(n):
	(x, y) = map(int, input().split())
	l[x - 1] += y
sum = 0
for kl in range(3001):
	if kl == 0:
		if v <= l[kl]:
			sum += v
			l[kl] -= v
		else:
			sum += l[kl]
			l[kl] = 0
	else:
		v1 = v
		if v1 <= l[kl - 1]:
			sum += v1
			l[kl - 1] -= v1
		else:
			sum += l[kl - 1]
			v1 -= l[kl - 1]
			l[kl - 1] = 0
			if v1 > 0:
				if v1 <= l[kl]:
					sum += v1
					l[kl] -= v1
				else:
					sum += l[kl]
					l[kl] = 0
print(sum)


(n, limit) = map(int, input().split())
arr = [0] * (3000 + 1)
for i in range(n):
	(a, b) = map(int, input().split())
	arr[a] += b
next = 0
fruits = 0
for i in range(1, 3001):
	v = limit
	temp = min(v, next)
	fruits += temp
	v -= temp
	temp = min(v, arr[i])
	fruits += temp
	next = arr[i] - temp
v = limit
fruits += min(v, next)
print(fruits)


import sys
import math
(n, v) = [int(x) for x in sys.stdin.readline().split()]
k = [0] * 3002
for i in range(n):
	(a, b) = [int(x) for x in sys.stdin.readline().split()]
	k[a] += b
i = 1
res = 0
while i <= 3001:
	val = 0
	if k[i - 1] < v:
		val = k[i - 1]
		res += val
		d = v - val
		if k[i] < d:
			res += k[i]
			k[i] = 0
		else:
			res += d
			k[i] = k[i] - d
	else:
		res += v
	i += 1
print(res)


(trees, collect) = map(int, input().split())
info = [0] * 3002
for x in range(trees):
	(day, fruits) = map(int, input().split())
	info[day] += fruits
prev = 0
cnt = 0
for x in range(1, 3002):
	temp = collect
	cnt += min(prev, collect)
	temp = collect - min(prev, collect)
	current = min(info[x], temp)
	cnt += current
	prev = info[x] - current
print(cnt)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
(n, v) = f()
l = [0] * 3003
for _ in range(n):
	(a, b) = f()
	l[a] += b
fromprevDay = 0
currDay = 0
temp = 0
ans = 0
for i in range(1, 3002):
	currDay = l[i]
	if fromprevDay + currDay <= v:
		ans += fromprevDay + currDay
		fromprevDay = 0
	elif fromprevDay >= v:
		ans += v
		fromprevDay = currDay
	else:
		ans += v
		temp = v - fromprevDay
		fromprevDay = currDay - temp
print(ans)


import sys, itertools as it

class pair:
	(x, y) = (0, 0)
array = [pair() for _ in range(4000)]
(n, v) = map(int, input().split())
for _ in range(n):
	(a, b) = map(int, input().split())
	array[a].y += b
	array[a + 1].x += b
ans = 0
for i in range(1, 3500):
	tmp = v
	ans += min(tmp, array[i].x)
	tmp -= min(tmp, array[i].x)
	ans += min(tmp, array[i].y)
	array[i + 1].x -= min(tmp, array[i].y)
print(ans)


(n, v) = [int(x) for x in input().split()]
l = [0] * 3002
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	l[a] += b
ans = 0
for i in range(1, 3002):
	left = v
	if l[i - 1]:
		ans += min(left, l[i - 1])
		left -= min(left, l[i - 1])
	ans += min(left, l[i])
	l[i] -= min(left, l[i])
print(ans)


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
(n, v) = map(int, input().split())
ls = [0] * 3005
for i in range(n):
	(a, b) = map(int, input().split())
	ls[a] += b
prev = 0
ans = 0
for i in range(1, 3005):
	curr = ls[i]
	if curr + prev <= v:
		ans += curr + prev
		curr = 0
	else:
		ans += v
		if prev < v:
			curr = curr + prev - v
	prev = curr
print(ans)


(n, v) = map(int, input().split(' '))
(result, day, trees) = (0, 1, {})
for i in range(n):
	(days, fruits) = map(int, input().split(' '))
	if days in trees:
		trees[days] += fruits
	else:
		trees[days] = fruits
while day <= 3001:
	to_collect = v
	if day - 1 in trees:
		x = trees[day - 1]
		trees[day - 1] = max(0, trees[day - 1] - v)
		to_collect = max(0, v - x)
		result += v - to_collect
	if day in trees:
		f = to_collect
		t = trees[day]
		trees[day] = max(0, trees[day] - to_collect)
		to_collect = max(0, to_collect - t)
		result += f - to_collect
	day += 1
print(result)


(n, k) = map(int, input().split(' '))
dict = {}
max = []
for i in range(n):
	(a, b) = map(int, input().split(' '))
	if a in dict:
		dict[a] += b
	else:
		dict[a] = b
for i in dict.copy():
	if i + 1 not in dict:
		dict[i + 1] = 0

def summa_fruit(dict):
	k = dict.values()
	sum = 0
	for i in k:
		sum += i
	return sum

def max_kol_fruit(dict, k):
	l = summa_fruit(dict)
	for i in sorted(dict):
		if i - 1 in dict:
			if dict[i - 1] >= k:
				dict[i - 1] = dict[i - 1] - k
			elif dict[i - 1] < k and dict[i] + dict[i - 1] >= k:
				dict[i] = dict[i] - k + dict[i - 1]
				dict[i - 1] = 0
			else:
				dict[i - 1] = 0
				dict[i] = 0
		elif dict[i] >= k:
			dict[i] = dict[i] - k
		else:
			dict[i] = 0
	return l - summa_fruit(dict)
print(max_kol_fruit(dict, k))


(n, v) = map(int, input().split())
d = [0] * 3003
a = []
j = 0
for i in range(n):
	(a, b) = map(int, input().split())
	d[a] += b
ans = 0
x = 0
for i in range(1, 3002):
	if d[i] + x < v:
		ans += d[i] + x
		x = 0
	else:
		t = max(v - x, 0)
		x = d[i] - t
		ans += v
print(ans)


(n, v) = map(int, input().rstrip().split())
li = [0] * 3002
t = 0
for i in range(n):
	(a, b) = map(int, input().rstrip().split())
	li[a] += b
for i in range(1, 3002):
	x = min(v, li[i - 1])
	y = min(li[i], v - x)
	li[i - 1] -= x
	li[i] -= y
	t += x + y
print(t)


from sys import stdin, stdout
input = stdin.readline
import math, bisect
(n, v) = map(int, input().split())
l = [0] * 3002
for i in range(n):
	(a, b) = map(int, input().split())
	l[a] += b
ans = 0
rem = 0
for i in range(1, 3002):
	if l[i] + rem <= v:
		ans += l[i] + rem
		rem = 0
	elif rem >= v:
		ans += v
		rem = l[i]
	else:
		ans += rem
		if l[i] >= v - rem:
			ans += v - rem
			rem = l[i] - (v - rem)
		else:
			ans += l[i]
			rem = 0
print(ans + min(v, rem))


def read_integer_pair():
	line = input()
	pair = line.split(' ')
	assert len(pair) == 2
	return (int(pair[0]), int(pair[1]))
(n, v) = read_integer_pair()
trees = {}
for i in range(n):
	(a, b) = read_integer_pair()
	if a in trees:
		trees[a] += b
	else:
		trees[a] = b
trees = list(trees.items())
trees.sort(key=lambda x: x[0])
prev_a = 0
prev_b = 0
apples = 0
for (a, b) in trees:
	dv = min(v, prev_b)
	apples += dv
	if a - prev_a != 1:
		dv = 0
	dv = max(min(v - dv, b), 0)
	apples += dv
	prev_a = a
	prev_b = b - dv
dv = min(v, prev_b)
apples += dv
print(apples)


N = 3005
(n, v) = map(int, input().split())
ripe = [0] * N
for i in range(n):
	(a, b) = map(int, input().split())
	ripe[a] += b
t = 0
ans = 0
for i in range(N):
	if ripe[i] + t <= v:
		ans += ripe[i] + t
		t = 0
	else:
		ans += min(t, v)
		ans += min(max(0, v - t), ripe[i])
		t = max(0, ripe[i] - max(0, v - t))
print(ans)


(n, v) = map(int, input().split())
t = []
for i in range(n):
	t.append(list(map(int, input().split())))
t.sort()
c = 0
a = 0
for d in range(3002):
	l = 0
	while c < n and t[c][0] < d - 1:
		c += 1
	while l < v and c < n and (t[c][0] <= d):
		if t[c][0] == d or t[c][0] == d - 1:
			if t[c][1] <= v - l:
				l += t[c][1]
				t[c][1] = 0
			else:
				t[c][1] -= v - l
				l = v
		if t[c][1] == 0:
			c += 1
	a += l
	if c >= n:
		break
print(a)


import sys
sys.setrecursionlimit(100000)
(n, v) = [int(x) for x in sys.stdin.readline().strip().split()]
arr = [0] * 3002
k = [0]
for i in range(n):
	(a, b) = [int(x) for x in sys.stdin.readline().strip().split()]
	if arr[a] == 0:
		k.append(a)
	arr[a] += b
k.sort()
count = 0
for i in k[1:]:
	if arr[i + 1] != 0:
		c = v
		al = min(c, arr[i - 1])
		count += al
		arr[i - 1] -= al
		c = c - min(c, al)
		count += min(c, arr[i])
		arr[i] -= min(c, arr[i])
	else:
		c = v
		al = min(c, arr[i - 1])
		count += al
		arr[i - 1] -= al
		c = c - min(c, al)
		count += min(c, arr[i])
		arr[i] -= min(c, arr[i])
		c = v
		count += min(c, arr[i])
		arr[i] -= min(c, arr[i])
print(count)


(n, v) = map(int, input().split())
li = []
for i in range(n):
	tp = [int(x) for x in input().split()]
	li.append(tp)
li.sort(key=lambda x: x[0])
d = {}
end = {}
distinct = set()
for i in range(n):
	if d.get(li[i][0], -1) == -1:
		d[li[i][0]] = i
	if i < n - 1 and li[i][0] != li[i + 1][0]:
		end[li[i][0]] = i
	distinct.add(li[i][0])
to = set()
for ele in distinct:
	if ele + 1 not in distinct:
		to.add(ele + 1)
for ele in to:
	distinct.add(ele)
distinct = list(distinct)
distinct.sort()
end[li[n - 1][0]] = n - 1
fruit = 0
i = 0
while i < len(distinct):
	ele = distinct[i]
	k = v
	if d.get(ele - 1, -1) != -1:
		start = d.get(ele - 1)
	else:
		start = d.get(ele)
	ennd = end[ele] if end.get(ele, -1) != -1 else end[ele - 1]
	for j in range(start, ennd + 1):
		if k == 0:
			break
		elif li[j][1] > 0:
			vl = min(li[j][1], k)
			k -= vl
			li[j][1] -= vl
			fruit += vl
	i += 1
print(fruit)


rip = [0] * 3050
(n, v) = [int(x) for x in input().split()]
for _ in range(n):
	(d, p) = [int(x) for x in input().split()]
	rip[d] += p
ans = 0
for i in range(1, 3050):
	t = min(v, rip[i - 1] + rip[i])
	rip[i] = rip[i] - max(0, t - rip[i - 1])
	ans += t
print(ans)


(n, v) = map(int, input().split())
N = [0 for i in range(3002)]
for i in range(n):
	(x, y) = map(int, input().split())
	N[x] += y
cost = 0
cur = 0
for i in range(3002):
	if N[i] + cur > v:
		cost += v
		if cur > v:
			cur = N[i]
		else:
			cur = N[i] - (v - cur)
	else:
		cost += N[i] + cur
		cur = 0
print(cost)


(n, v) = map(int, input().split())
(d, s) = ({}, 0)
for i in range(n):
	(a, b) = map(int, input().split())
	d[a] = d.get(a, 0) + b
	s += b
r = v
for i in sorted(d.keys()):
	d[i] -= min(d[i], r)
	(r, b) = (v, min(d[i], v))
	d[i] -= b
	if i + 1 in d:
		r -= b
print(s - sum(d.values()))


l = lambda : map(int, input().split())
(n, v) = l()
t = {}
for _ in ' ' * n:
	(x, y) = l()
	t[x] = t.get(x, 0) + y
s = 0
for i in range(min(t), max(t) + 2):
	us = v
	x = min(us, t.get(i - 1, 0))
	s += x
	us -= x
	t[i - 1] = t.get(i - 1, 0) - x
	x = min(us, t.get(i, 0))
	s += x
	t[i] = t.get(i, 0) - x
print(s)


(n, v) = map(int, input().split())
(s, t) = (0, [0] * 3002)
for i in range(n):
	(a, b) = map(int, input().split())
	t[a] += b
for d in range(1, 3002):
	ds = min(t[d - 1], v)
	s += ds
	ds = min(t[d], v - ds)
	t[d] -= ds
	s += ds
print(s)


from collections import defaultdict
dd = defaultdict(int)
(n, v) = map(int, input().split())

def foo(day, toadd):
	z = 0
	if newDD[day] < toadd:
		z += newDD[day]
		newDD[day] = 0
	else:
		z += toadd
		newDD[day] -= toadd
	return z
for _ in range(n):
	(temp1, temp2) = map(int, input().split())
	dd[temp1] += temp2
newDD = dict(sorted(dd.items()))
ans = 0
mxday = max(newDD.keys())
for key in range(1, mxday + 2):
	V = v
	if key - 1 in newDD:
		if newDD[key - 1] > 0:
			temp = foo(key - 1, V)
			V -= temp
			ans += temp
	if key in newDD:
		if V > 0:
			ans += foo(key, V)
print(ans)


(n, v) = map(int, input().split())
a = []
for x in range(n):
	p = list(map(int, input().split()))
	a.append((p[0], p[1]))
a.sort()
arr = [0] * 4000
for x in range(n):
	arr[a[x][0]] += a[x][1]
	tmp = max(0, arr[a[x][0]] - v)
	arr[a[x][0]] -= tmp
	arr[a[x][0] + 1] += tmp
	arr[a[x][0] + 1] = min(arr[a[x][0] + 1], v)
print(sum(arr))


(n, v) = map(int, input().split())
f = [0] * 3005
for i in range(n):
	(a, b) = map(int, input().split())
	f[a] += b
day = 1
down = 0
collect = 0
while day <= 3001:
	curr = f[day]
	if curr + down <= v:
		collect += curr + down
		curr = 0
	else:
		collect += v
		if down < v:
			curr = curr + down - v
	day += 1
	down = curr
print(collect)


import sys

def minp():
	return sys.stdin.readline().strip()
A = [0] * 3005
(n, v) = map(int, minp().split())
for i in range(n):
	(a, b) = map(int, minp().split())
	A[a] += b
r = 0
for i in range(1, len(A) - 1):
	z = min(v, A[i - 1])
	A[i - 1] -= z
	w = min(v - z, A[i])
	A[i] -= w
	r += z + w
print(r)


from collections import *
from heapq import *
(n, k) = map(int, input().split())
ans = 0
g = defaultdict(list)
for i in range(n):
	(a, b) = map(int, input().split())
	g[a].append(b)
h = []
for day in range(1, 3002):
	if day in g:
		for i in g[day]:
			heappush(h, [day, i])
	sobr = k
	while h and sobr:
		if h[0][0] + 1 < day:
			heappop(h)
		else:
			f = heappop(h)
			if f[1] <= sobr:
				ans += f[1]
				sobr -= f[1]
			else:
				ans += sobr
				heappush(h, [f[0], f[1] - sobr])
				sobr = 0
print(ans)


from collections import defaultdict

def main():
	MAX = 3002
	(n, v) = map(int, input().split(' '))
	m = defaultdict(list)
	for i in range(n):
		(ai, bi) = map(int, input().split(' '))
		m[ai].append(bi)
	a = [[] for i in range(MAX)]
	for i in range(0, MAX):
		if i in m:
			a[i] = m[i]
		else:
			a[i] = [0]
	r = 0
	l = 0
	for i in range(1, MAX):
		xs = []
		vv = v
		for ai in a[i]:
			y = 0
			if l > 0 and vv > 0:
				y = min(vv, l)
				r += y
				vv -= y
				l -= y
			x = min(vv, ai)
			vv -= x
			r += x
			if ai - x > 0:
				xs.append(ai - x)
		l = 0
		for x in xs:
			if x > 0:
				l += x
	return r
print(main())