Vanya wants to pass n exams and get the academic scholarship. He will get the scholarship if the average grade mark for all the exams is at least avg. The exam grade cannot exceed r. Vanya has passed the exams and got grade a_{i} for the i-th exam. To increase the grade for the i-th exam by 1 point, Vanya must write b_{i} essays. He can raise the exam grade multiple times.

What is the minimum number of essays that Vanya needs to write to get scholarship?


-----Input-----

The first line contains three integers n, r, avg (1 ≤ n ≤ 10^5, 1 ≤ r ≤ 10^9, 1 ≤ avg ≤ min(r, 10^6)) — the number of exams, the maximum grade and the required grade point average, respectively.

Each of the following n lines contains space-separated integers a_{i} and b_{i} (1 ≤ a_{i} ≤ r, 1 ≤ b_{i} ≤ 10^6).


-----Output-----

In the first line print the minimum number of essays.


-----Examples-----
Input
5 5 4
5 2
4 7
3 1
3 2
2 5

Output
4

Input
2 5 4
5 2
5 2

Output
0



-----Note-----

In the first sample Vanya can write 2 essays for the 3rd exam to raise his grade by 2 points and 2 essays for the 4th exam to raise his grade by 1 point.

In the second sample, Vanya doesn't need to write any essays as his general point average already is above average.

Difficulty: interview

Starter code:

Solutions:
import sys
n,r,avg=list(map(int,input().split()))
L=[]
tot=0
for i in range(n):
    L.append(list(map(int,input().split())))
    L[i][0],L[i][1]=L[i][1],L[i][0]
    tot+=L[i][1]
    L[i][1]=r-L[i][1]
req=avg*n
L.sort()
ind=0
ans=0
while(ind<n and req>tot):
    diff=req-tot
    if(L[ind][1]>=diff):
        ans+=diff*L[ind][0]
        tot+=diff
        L[ind][1]-=diff
    else:
        ans+=L[ind][1]*L[ind][0]
        tot+=L[ind][1]
        L[ind][1]=0
    ind+=1
print(ans)


__author__ = 'PrimuS'

n, r, a = (int(x) for x in input().split())
marks = [[0, 0]] * n
s = 0
for i in range(n):
    ss = input()
    marks[i] = [int(x) for x in ss.split()]
    s += marks[i][0]

if (s / n) >= a:
    print(0)
else:
    x = a * n - s

    def ccmp(b):
        return b[1]
    marks.sort(key=ccmp)

    i = 0
    res = 0
    while x > 0:
        y = min(x, r - marks[i][0])
        x -= y
        res += marks[i][1] * y
        i += 1

    print(res)


def main():
    n, r, avg = map(int, input().split())

    need = avg * n

    d = sorted([list(map(int, input().split())) for _ in range(n)], key = lambda x: x[1])
    cur = sum(x[0] for x in d)
    #print(d, cur)
    ret = 0
    left = need - cur
    if left <= 0:
        return 0
    for x in d:
        can = min(r - x[0], left)
        ret += can * x[1]
        left -= can
        if left == 0:
            return ret

print(main())

n, r, avg = list(map(int, input().split()))

array = []
s = 0

for index in range(0, n):
    array.append(list(map(int, input().split())))
    s += array[index][0]

array.sort(key=lambda x: x[1])
index = 0
answer = 0
while s // n < avg :
    if s + r - array[index][0] >= avg * n:
        answer += array[index][1] * (avg * n - s)
        break
    s += r - array[index][0]
    answer += array[index][1] * (r - array[index][0])
    index += 1

print(answer)


n,r,avg = list(map(int, input().split()))
score = []
total = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    score.append((b, a))
    total += a
need_point = max(0, avg * n - total)
score.sort()
ans = 0
for b, a in score:
    if need_point == 0:
        break
    if a < r:
        ans += b * min(r - a, need_point)
        need_point -= min(r - a, need_point)
print(ans)    






__author__ = 'valeriy.shevchuk'

from math import ceil

n, r, avg = map(int, input().split())
data = []
sum_v = 0

for i in range(n):
    a, b = map(int, input().split())
    sum_v += a
    data.append((a, b))

need = ceil(max(avg * n - sum_v, 0))
data = sorted(data, key=lambda x: x[1])

ref = 0
for i in range(len(data)):
    if need <= 0:
        break

    if data[i][0] < r:
        grades = min(r - data[i][0], need)
        ref += grades * data[i][1]
        need -= grades

print(ref)

n, r, avg = list(map(int, input().split()))
exams, need, ans = [], avg * n, 0
for x in range(n):
    a, b = list(map(int, input().split()))
    exams.append([b, a])
    need -= a
exams.sort()
i = 0
while need > 0 and i < n:
    ans += exams[i][0] * min(r - exams[i][1], need)
    need -= min(r - exams[i][1], need)
    i += 1
print(ans)


n, r, avg = list(map(int, input().split()))
a = []
cur = 0
for i in range(n):
    t1, t2 = list(map(int, input().split()))
    cur += t1
    a.append((t2, t1))

a = sorted(a)
ans = 0
avg = avg * n
for i in range(n):
    if cur >= avg:
        break
    need = avg - cur
    temp = min(need, r - a[i][1])
    cur += temp
    ans += temp * a[i][0]


print(ans)

    


first = input().split()
n = int(first[0])
r = int(first[1])
avg = int(first[2])
marks = {}
total = 0
essays = []
for i in range(n):
    inp = input().split()
    inp[0] = int(inp[0])
    inp[1] = int(inp[1])
    total += inp[0]
    essays.append(inp[1])
    if inp[1] in marks:
        marks[inp[1]].append(inp[0])
    else:
        marks[inp[1]] = [inp[0]]

if total/n >= avg:
    print(0)
else:
    out = 0
    essays = list(set(essays))
    essays.sort()
    deficit = avg * n - total
    ind = 0
    while deficit > 0:
        current = essays[ind]
        for i in range(len(marks[current])):
            if marks[current][i] < r:
               x = r - marks[current][i]
               if deficit >= x:
                   out += current * x
                   deficit -= x
               else:
                   out += current * deficit
                   deficit = 0
               if deficit == 0:
                   break
        ind += 1
    print(out)
                


line = input().split(' ')
n = int(line[0])
r = int(line[1])
avg = int(line[2])

class Exam:
    
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __repr__(self):
        return repr((self.a, self.b))
        

i = 0
s = 0
lst = []
while i < n:
    line = input().split(' ')
    a = int(line[0])
    b = int(line[1])
    lst.append(Exam(a, b))
    s += a
    i += 1

lst.sort(key = lambda exam: exam.b)

ans = 0
avg *= n
for exam in lst:
    if s >= avg:
        break
    ans += min(r - exam.a, avg - s) * exam.b
    s += min(r - exam.a, avg - s)

print(ans)


from sys import stdin


def main():
    n, r, avg = list(map(int, stdin.readline().strip().split()))
    aa, bb = [], []
    for _ in range(n):
        a, b = list(map(int, stdin.readline().strip().split()))
        aa.append(a)
        bb.append(b)
    now = sum(aa)
    ineed = n * avg
    if now >= ineed:
        return 0
    pref = sorted(list(range(n)), key=bb.__getitem__)
    tot = 0
    for i in pref:
        a, b = aa[i], bb[i]
        delta = min(ineed - now, r - a)
        tot += b * delta
        now += delta
        if now == ineed:
            return tot


print(main())


n, r, avg = list(map(int, input().split()))
a = [list(reversed(list(map(int, input().split())))) for i in range(n)]
a.sort()
cur = 0
req = avg * n
for i in range(n):
    cur += a[i][1]
i = 0
ans = 0
while i < n and cur < req:
    d = min(req - cur, r - a[i][1])
    ans += min(req - cur, r - a[i][1]) * a[i][0]
    i += 1
    cur += d
print(ans)
    


n, r, avg = [int(i) for i in input().split()]
a = [0] * n
b = [[0] * 2 for i in range(n)]
for j in range(n):
    a[j], b[j][0] = [int(i) for i in input().split()]
    b[j][1] = j
b.sort()
mid = -1
sum1 = sum(a)
res = 0
hod = 0
sumOLD = 0
if sum1 / n < avg:
    while mid < avg:
        sumOLD = sum1
        sum1 += min(r - a[b[hod][1]], avg * n - sumOLD)
        res += b[hod][0] * min(r - a[b[hod][1]], avg * n - sumOLD)
        hod += 1
        mid = sum1 / n
    print(res)
else:
    print(0)



n, r, avg = map(int, input().split())
avg *= n
a = [0] * n
b = [0] * n
mas = [[0, 0]] * n
summ = 0
for i in range(n):
    a[i], b[i] = map(int, input().split())
    summ += a[i]
    mas[i] = [b[i], a[i] - r]
mas.sort()
for i in range(n):
    mas[i][1] *= -1
i = 0
cnt = 0
while i < n and summ < avg:
    cnt += min(mas[i][1], avg - summ) * mas[i][0]
    summ += min(mas[i][1], avg - summ)
    i += 1
print(cnt)

__author__ = 'Ekaterina'
n, r, avg = (int(m) for m in input().split())
exams = []
for i in range(n):
    input_i = [int(m) for m in input().split()]
    exams.append([input_i[1], input_i[0]])
exams.sort()
current_sum = exams[0][1]
works_to_do = 0
for x in range(1, n):
    current_sum += exams[x][1]
needed_points = avg*n - current_sum
if needed_points <= 0:
    print(0)
else:
    j = 0
    while needed_points > 0:
        points_subject = r - exams[j][1]
        if needed_points == points_subject:
            works_to_do = works_to_do + exams[j][0]*points_subject
            break
        elif needed_points < points_subject:
            works_to_do = works_to_do + exams[j][0]*needed_points
            break
        elif needed_points > points_subject:
            needed_points = needed_points - points_subject
            works_to_do = works_to_do + exams[j][0]*points_subject
        j += 1
    print(works_to_do)

stat = []
n, r, avg = map(int, input().split(' '))
for i in range(n):
    a, b = map(int, input().split(' '))
    stat.append([a, b, r-a])

req = n * avg
curr = sum([i[0] for i in stat])
need = req - curr

stat.sort(key = lambda x: x[1])
        
curr = 0
tot = 0
while need > 0:
    if stat[curr][2] <= need:
        tot += stat[curr][2] * stat[curr][1]
        need -= stat[curr][2]
        curr += 1
    else:
        tot += stat[curr][1] * need
        need = 0
print(tot)

n, r, avg = list(map(int, input().split()))
total = 0
exams = []
for i in range(n):
    score, cost = list(map(int, input().split()))
    total += score
    exams.append((cost,score))
need = n*avg - total
result = 0
exams.sort()
for cost, score in exams:
    if need <= 0:
        break
    x = min(need, r-score)
    result += cost*x
    need -= x
print(result)


__author__ = 'Rakshak.R.Hegde'
n, r, avg = map(int, input().split())
ab = []
d = n * avg
for i in range(n):
    a, b = map(int, input().split())
    d -= a
    ab.append((b, a))
ab.sort()
cost = 0
for t in ab:
    if d <= 0: break
    if t[1] < r:
        m = min(d, r - t[1])
        cost += m * t[0]
        d -= m
print(cost)

import operator
n,r,avg=list(map(int,input().split()))
Goal=n*avg
Sum,ans=0,0
Exam=[]
for i in range(n):
    a,b=list(map(int,input().split()))
    Sum+=a
    Exam.append([a,b])
Exam.sort(key=operator.itemgetter(1))
#print(Exam)
i=0
while Sum<Goal and i<n:
    d=min(Goal-Sum,r-Exam[i][0])
    ans+=d*Exam[i][1]
    Sum+=d
    i=i+1
print(ans)


import sys
import math

n, r, avg = [int(x) for x in (sys.stdin.readline()).split()]
res = 0
k = []
vsum = 0
for i in range(n):
    a, b = [int(x) for x in (sys.stdin.readline()).split()]
    if(a >= r):
        vsum += r
    else:
        vsum += a
        k.append((r - a, b))
        
k.sort(key = lambda x: x[1])

val = n * avg - vsum
if(val <= 0):
    print(0)
    return

z = 0
i = 0
while(z < val):
    z += k[i][0]
    res += k[i][1] * k[i][0]
    i += 1
    
i -= 1
if(z > val):
    res -= (z - val) * k[i][1]
    print(res)
else:
    print(res)
        


    


n, r, avg = list(map(int, input().split()))

a = []
sum = int(round(avg*n))
sum1 = 0
res = 0
for i in range(n):
    x, y = list(map(int, input().split()))
    a.append([y, x])
    sum1 += x

a.sort()
i = 0
while sum > sum1:
    if sum - sum1 > r - a[i][1]:
        sum1 += (r - a[i][1])
        res += (r - a[i][1])*a[i][0]
        i += 1
    else:
        res += (sum - sum1)*a[i][0]
        sum1 = sum

print(res)






n, r, avg = list(map(int, input().split(' ')))

exams = [list(map(int, input().split(' '))) for _ in range(n)]

exams.sort(key=lambda x: x[1])

total = n*avg
cur = sum(e[0] for e in exams)
essays = 0
for e in exams:
  if cur >= total:
    break
  its = min(r-e[0], total-cur)
  cur += its
  e[0] += its
  essays += its * e[1]

print(essays)


import operator
n,r,avg=list(map(int,input().split()))
x,y=0,0
s=0
l=[]
for i in range(n):
    x,y=list(map(int,input().split()))
    l.append([x,y])
    s+=x
l.sort(key=operator.itemgetter(1))
s=n*avg-s
ans,i=0,0
while s>0 and i<n:
    ans+=min(s,r-l[i][0])*l[i][1]
    s-=min(s,r-l[i][0])
    i+=1
print(ans)
    



n,r,avg = list(map(int, input().split(' ')))
L = []
for i in range(n) :
    x = list(map(int, input().split(' ')))
    L.append(x)

L.sort(key = lambda x : x[1])

s = 0
for i in L :
    s += i[0]

need = avg*n - s

if need <= 0 :
    ans = 0
else :   
    ans = 0
    start = 0
    while(need > 0) :
        a = L[start][0]
        b = L[start][1]
        k = r-a
        if k > need :
            ans += need*b
            need = 0
        else :
            ans += k*b
            need -= k
        start += 1
print(ans)


t = input().split()
n = int(t[0])  # ���������� ���������
r = int(t[1])  # ������������ ������
avg = int(t[2])  # ���������� ��������� ������� ����
a = []  # ������ � ������� �� ���������
    
for i in range(n):
    a.append(input().split())
    t = int(a[i][0])
    a[i][0] = int(a[i][1])
    a[i][1] = t

a = sorted(a)
# ������������� �� ���������� ������ ���������

ref = 0  # ���������� ���������

new = 0
for i in range(n):
    new += a[i][1]
new /= n
# ��������� ��������� ������� ��������������

i = 0
while (new < avg) and (i < n):
    x = min(r-a[i][1], round((avg-new)*n))  # ��, ������� ������ ����� �������� ������
    new += (1/n) * x  # �������� ������� ��������������
    ref += a[i][0] * x  # �������� ���������� ���������
    i += 1
    
print(round(ref))