Chef loves cooking. Also, he is very hygienic. Hence, Chef grows his own vegetables in his mini kitchen garden. He has $M$ lanes in which he grows vegetables. The $ith$  lane has $Ai$ vegetables growing in it.

Vegetables in $ith$ lane become edible on day $Di$ and day $Di+1$(that is, the vegetables are edible only on days $Di$ and $Di+1$,where $Di+1$ is the next day of $Di$).   For Example, if $Di$ is 2, then vegetable is edible on day 2 and day 3 only.   If not collected in these days, they cannot be cooked.

Also, Chef is a lone worker. Hence, with respect to his capacity, he can collect only $V$ vegetables per day.
But, Chef is a hard worker, and is willing to work every day, starting from day 1.

Chef is busy sowing the seeds. So, he assigns you the task to find out the maximum number of vegetables he can collect, provided that he collects optimally.

-----Input:-----
- First line contains of 2 space separated integers $M$ and $V$, number of lanes and capacity of Chef.
- Next $M$ lines follow
- Each $ith$ line contains 2 space separated integers, $Di$ and $Ai$, the day when the vegetable of the $ith$ lane become edible and the number of vegetables in that lane.

-----Output:-----
For each testcase, output in a single integer, that is the maximum number of vegetables that can be cooked

-----Constraints-----
- $1 \leq M,V \leq 3000$
- $1 \leq Di,Ai \leq 3000$

-----Subtasks-----
- 20 points : $1 \leq M \leq 100$
- 30 points : $1 \leq M \leq 1000$
- 50 points : $Original  Constraints$

-----Sample Input 1:-----
2 4
1 6
2 5

-----Sample Output 1:-----
11

-----Sample Input 2:-----
3 3
1 4
6 2
5 3

-----Sample Output 2:-----
9

-----EXPLANATION:-----
In the first sample, in order to obtain the optimal answer, you should do the following:-
- On day 1, collect 4 vegetables from lane 1
- On day 2, collect 2 vegetables from lane 1 and 2 vegetables from lane 2
- On day 3, collect 3 vegetables from lane 2
In the first sample, in order to obtain the optimal answer, you should do the following:-
- On day 1, collect 3 vegetables from lane 1
- On day 2, collect 1 vegetable from lane 1
- On day 5, collect 3 vegetables from lane 3
- On day 6, collect 2 vegetables from lane 2

Difficulty: interview

Starter code:

Solutions:

from sys import stdin,stdout
input=stdin.readline
print=stdout.write
m,v=map(int,input().split())
a=[]
t=0
for i in range(m):
 x,y=map(int,input().split())
 a.append([x,y])
a.sort()
d=0
re=0
equip=0
for x,y in a:
 if d<x:
  d=x
  if y<=v:
   equip+=y
   re=v-y
   if y==v:
    d+=1
    re=0
  elif y>v and y<2*v:
   equip+=y
   d+=1
   re=2*v-y
  else:
   equip+=2*v
   d+=2
   re=0
 elif d==x:
  if re==0:
   if y<=v:
    equip+=y
    re=v-y
    if y==v:
     d+=1
     re=0
   elif y>=v and y<2*v:
    equip+=y
    d+=1
    re=2*v-y
   else:
    equip+=2*v
    d+=2
    re=0
  else:
   if y<re:
    equip+=y
    re-=y
   elif y==re:
    equip+=y
    re=0
    d+=1
   elif y>re:
    d+=1
    equip+=re
    y-=re
    if y<v:
     equip+=y
     re=v-y
    elif y>=v:
     equip+=v
     re=0
     d+=1
 elif d==x+1:
  if re==0:
   if y<v:
    equip+=y
    re=v-y
   elif y>=v:
    equip+=v
    re=0
    d+=1
  else:
   if y<=re:
    equip+=y
    re-=y
    if re==0:d+=1
   elif y>re:
    equip+=re
    re=0
    d+=1
print(str(equip))

m,v = map(int, input().split())
a = [ 0 for x in range(3500)]
b = []
for i in range(m):
 b.append(list(map(int,input().split())))
b.sort()
#print(b)
for i in b:
 d = i[0]
 l = i[1]
 if a[d]+l<=v:
  a[d]+=l
 else:
  if a[d]>v:
   a[d+1]+=l
  else:
   total = a[d]+l
   a[d]=v
   a[d+1]+=total-v
ans = 0
for j in a:
 ans += min(j,v)
print(ans)

m,v = map(int, input().split())
a = [ 0 for i in range(3500)]
b = []
for i in range(m):
 d, l = map(int,input().split())
 b.append([d, l ])
b.sort()
#print(b)
for i in b:
 d = i[0]
 l = i[1]
 if a[d]+l<=v:
  a[d]+=l
 else:
  if a[d]>v:
   a[d+1]+=l
  else:
   total = a[d]+l
   a[d]=v
   a[d+1]+=total-v
ans = 0
for i in a:
 ans += min(i,v)
print(ans)

def ans(dic,v):
 count=0
 for i in range(1,3002):
  try:
   k=dic[i-1]
   l=v-k
   if k<=v:
    count+=k
    if l>dic[i]:
     count+=dic[i]
     dic[i]=0
    else:
     count+=l
     dic[i]-=l
   else:
    count+=v
  except:
   continue
 return count

m,v=[int(x) for x in input().split()]
dic={i:0 for i in range(3002)}
for i in range(m):
 try:
  d,a=[int(x) for x in input().split()]
  dic[d]+=a
 except:
  continue
print(ans(dic,v))
 
 


def ans(dic,v):
 count=0
 for i in range(1,3002):
  try:
   k=dic[i-1]
   l=v-k
   if k<=v:
    count+=k
    if l>dic[i]:
     count+=dic[i]
     dic[i]=0
    else:
     count+=l
     dic[i]-=l
   else:
    count+=v
  except:
   continue
 return count

m,v=[int(x) for x in input().split()]
dic={i:0 for i in range(3002)}
for i in range(m):
 d,a=[int(x) for x in input().split()]
 dic[d]+=a
print(ans(dic,v))