Summer holidays! Someone is going on trips, someone is visiting grandparents, but someone is trying to get a part-time job. This summer Noora decided that she wants to earn some money, and took a job in a shop as an assistant.

Shop, where Noora is working, has a plan on the following n days. For each day sales manager knows exactly, that in i-th day k_{i} products will be put up for sale and exactly l_{i} clients will come to the shop that day. Also, the manager is sure, that everyone, who comes to the shop, buys exactly one product or, if there aren't any left, leaves the shop without buying anything. Moreover, due to the short shelf-life of the products, manager established the following rule: if some part of the products left on the shelves at the end of the day, that products aren't kept on the next day and are sent to the dump.

For advertising purposes manager offered to start a sell-out in the shop. He asked Noora to choose any f days from n next for sell-outs. On each of f chosen days the number of products were put up for sale would be doubled. Thus, if on i-th day shop planned to put up for sale k_{i} products and Noora has chosen this day for sell-out, shelves of the shop would keep 2·k_{i} products. Consequently, there is an opportunity to sell two times more products on days of sell-out.

Noora's task is to choose f days to maximize total number of sold products. She asks you to help her with such a difficult problem.


-----Input-----

The first line contains two integers n and f (1 ≤ n ≤ 10^5, 0 ≤ f ≤ n) denoting the number of days in shop's plan and the number of days that Noora has to choose for sell-out.

Each line of the following n subsequent lines contains two integers k_{i}, l_{i} (0 ≤ k_{i}, l_{i} ≤ 10^9) denoting the number of products on the shelves of the shop on the i-th day and the number of clients that will come to the shop on i-th day.


-----Output-----

Print a single integer denoting the maximal number of products that shop can sell.


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

Output
10
Input
4 1
0 2
0 3
3 5
0 6

Output
5


-----Note-----

In the first example we can choose days with numbers 2 and 4 for sell-out. In this case new numbers of products for sale would be equal to [2, 6, 2, 2] respectively. So on the first day shop will sell 1 product, on the second — 5, on the third — 2, on the fourth — 2. In total 1 + 5 + 2 + 2 = 10 product units.

In the second example it is possible to sell 5 products, if you choose third day for sell-out.

Difficulty: interview

Starter code:

Solutions:
n, f = list(map(int, input().split(' ')))
res = 0
wow = []
for a0 in range(n):
    k, l = list(map(int, input().split(' ')))
    res += min(k, l)
    wow.append(min(2*k, l) - min(k, l))
wow = sorted(wow)
i = len(wow)-1
for a0 in range(f):
    res += wow[i]
    i -= 1
print(res)


from sys import stdin, stdout
import math

n, k = map(int, stdin.readline().split())
values = []
ans = 0

for i in range(n):
    a, b = map(int, stdin.readline().split())
    ans += min(a, b)
    
    if a < b:
        b -= a
        values.append(min(a, b))



values.sort()
for v in values[::-1]:
    if not k:
        break
    
    ans += v
    k -= 1


stdout.write(str(ans))

n, f = list(map(int, input().split()))
d = []
for i in range(n):
    d.append(list(map(int, input().split())))
d.sort(reverse=True, key=lambda x: min(2 * x[0], x[1]) - min(x[0], x[1]))
res = 0
for i in range(n):
    if i < f:
        res += min(2 * d[i][0], d[i][1])
    else:
        res += min(d[i][0], d[i][1])
print(res)


l = input().strip().split()
n , f = int(l[0]) , int(l[1])

lst = []
base = []
for i in range(n):
    l = input().split()
    k , l = int(l[0]) , int(l[1])
    base.append(min(l,k))
    lst.append(max(0, min(k, l - k)))
    # print('>>',base[-1], lst[-1])
lst = sorted(lst, reverse=True)
print(sum(lst[:f]) + sum(base))

import sys

def solve():
    n, f = map(int, input().split())
    k = [0] * n
    l = [0] * n
    d = [0] * n

    for i in range(n):
        ki, li = map(int, sys.stdin.readline().split())
        k[i] = ki
        l[i] = li

        if 2*ki > li:
            d[i] = max(li - ki, 0)
        else:
            d[i] = ki

    d.sort(reverse=True)

    ans = sum(d[:f]) + sum(min(k[i], l[i]) for i in range(n))

    print(ans)



def __starting_point():
    solve()
__starting_point()

import sys
input = sys.stdin.readline

n, f = list(map(int, input().split()))

surplus = []
sold = []

for i in range(n):
  p, c = list(map(int, input().split()))
  sold.append(min(p, c))
  unsold = max(0, c - p)
  more = min(unsold, p)
  surplus.append(more)
  
surplus.sort(reverse=True)
print(sum(surplus[:f]) + sum(sold))


n, f = list(map(int, input().split()))
ans = 0
L = []
for _ in range(n):
    p, c = list(map(int, input().split()))
    s = min(p, c)
    sf = min(2*p, c)
    ans += s
    L.append(sf-s)
L.sort(reverse=True)
ans += sum([x for x in L[:f] if x>0])
print(ans)


n,f=list(map(int,input().split()))
a=[0]*n
b=[0]*n
z=[0]*n
for i in range (n):
    a1,b1=list(map(int,input().split()))
    a[i]=a1
    b[i]=b1
for i in range(n):
    z1=min(2*a[i],b[i])-min(a[i],b[i])
    z[i]=z1
z.sort()
c=0
for i in range(n):
    c+=min(a[i],b[i])
for i in range(n-1,n-f-1,-1):
    c+=z[i]
print(c)
    


n,f = list(map(int,input().split()))
r = []
for _ in range(n):
  a,b = list(map(int,input().split()))
  if 2*a <= b:
    r.append((a,a))
  elif a <= b:
    r.append((b-a,a))
  else:
    r.append((0,b))
ret = 0
r1 = sorted(r)[::-1]
for a,b in r1[:f]:
  ret += a + b
for a,b in r1[f:]:
  ret += b
print(ret)


#! /usr/bin/env python3

from collections import namedtuple

n, f = (int(i) for i in input().split())

Day = namedtuple('Day', ('cur', 'diff'))

a = []

for i in range(n):
    k, l = (int(j) for j in input().split())
    a.append(Day((min(k, l)), min(2 * k, l) - min(k, l)))

a.sort(key=lambda day: day.diff, reverse=True)

print(sum(day.diff for day in a[:f]) + sum(day.cur for day in a))


n,f = list(map(int, input().split()))
a = []
for _ in range(n):
    k,l = list(map(int, input().split()))
    a.append( ( -(min(l, k*2)-min(l,k)) , min(l, k)) )

a.sort()

#print(a)

tot = 0;
for i in range(0,f):
    tot += -a[i][0] + a[i][1]

for i in range(f,n):
    tot += a[i][1]

print(tot)



#!/usr/bin/env python

import sys

n, f = list(map(int, sys.stdin.readline().split()))
increments = []
without_increments = 0
for __ in range(n):
    prod, cust = list(map(int, sys.stdin.readline().split()))
    increments.append(max(0, min(prod * 2, cust) - prod))
    #print(increments)
    without_increments += min(prod, cust)
    #print( without_increments )
print(without_increments + sum(sorted(increments, reverse=True)[:f]))


def calc_income(cnt, customers):
    return min(cnt, max(0, customers - cnt))


n, f = map(int, input().split())

days = [tuple(map(int, input().split())) for i in range(n)]
days.sort(key=lambda elem: -calc_income(*elem))

ans = sum(map(lambda elem: min(elem[0], elem[1]), days))
for cnt, customers in days[:f]:
    ans += calc_income(cnt, customers)

print(ans)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    n, f = [int(x) for x in input().split()]
    a = []
    for i in range(n):
        k, m = [int(x) for x in input().split()]
        x = 0
        if k >= m:
            x = 0
        elif m < 2 * k:
            x = m - k
        else:
            x = k
        a.append([k, m, x])
    a.sort(key=lambda tup: tup[2], reverse=True)
    for i in range(f):
        a[i][0] += a[i][2]
    for i in range(n):
        a[i][2] = a[i][0] if a[i][0] < a[i][1] else a[i][1]
    print(sum(a[i][2] for i in range(n)))

def __starting_point():
    main()

__starting_point()

import math
import re



n, f = list(map(int, input().split()))
k = []
l = []

d = []
d1 = []
for i in range(n):
    k, l = list(map(int, input().split()))
    if k >= l:
        d.append(0)
        d1.append(l)
    elif 2*k >= l:
        d.append(l - k)
        d1.append(k)
    else:
        d.append(k)
        d1.append(k)





d = sorted(d, reverse= True)

print(sum(d[:f]) + sum(d1))



# n, m = map(int, input().split())
# w = []
# c = []
# for i in range(n):
#     x, y = map(int, input().split())
#     w.append(x)
#     c.append(y)
#
# A = [[0] * (m + 1) for i in range(n)]
#
#
# for k in range(n):
#       for s in range(1, m + 1):
#             if s >= w[k]:
#                 A[k][s] = max(A[k - 1][s], A[k - 1][s - w[k]] + c[k])
#             else:
#                 A[k][s] = A[k-1][s]
#
# print(A[n - 1][m])

    # arr = list(map(int, input().split()))
# res = 0
# a = {math.pow(2, i) for i in range(35)}
# for i in range(n-1):
#     for j in range(i+1,n):
#         if arr[i] + arr[j] % 2 % 2 % 2 % 2 % 2 in a:
#             res += 1
#
# print(res)


# arr = list(map(int, input().split()))
# m = int(input())
# spis = list(map(int, input().split()))
#
# arr1 = sorted(arr, reverse=True)
# a = [n - arr1.index(arr[el - 1]) for el in spis]
# print(' '.join(map(str, a)))


# -*- coding: utf-8 -*-

import sys
import os
import math

# input_text_path = __file__.replace('.py', '.txt')
# fd = os.open(input_text_path, os.O_RDONLY)
# os.dup2(fd, sys.stdin.fileno())

n, f = map(int, input().split())

A = []

normal_sell_total = 0
for i in range(n):
    product_num, client_num = map(int, input().split())

    if product_num >= client_num:
        normal_sell_num = client_num
    else:
        normal_sell_num = product_num
    normal_sell_total += normal_sell_num

    if product_num * 2 >= client_num:
        double_sell_num = client_num
    else:
        double_sell_num = product_num * 2

    diff = double_sell_num - normal_sell_num
    A.append(diff)

A.sort(reverse=True)
increased_sell_num = sum(A[:f])
print(normal_sell_total + increased_sell_num)

import sys

n, f =  list(map(int, sys.stdin.readline().rstrip().split()))

li = []
li2 = []
for i in range(n):
    k, l = list(map(int, sys.stdin.readline().rstrip().split()))
    li.append((k, l))

li = sorted(li, key=lambda x: min(x[0]*2,x[1])-min(x[0],x[1]))

result = 0
for i in range(n):
    if i >= n-f:
        result += min(li[i][0]*2,li[i][1])
    else:
        result += min(li[i][0],li[i][1])



sys.stdout.write(str(result))



n, f = list(map(int, input().split()))

products_and_clients_per_day = []

for i in range(n):
  k, l = list(map(int, input().split()))
  normal_sales = min(k, l)
  double_sales = min(2*k, l)
  sell_out_profit = double_sales - normal_sales
  products_and_clients_per_day.append((k,l, sell_out_profit))


products_and_clients_per_day.sort(key=lambda x: x[2], reverse=True)

res = 0

for i in range(f):
  k, l, sell_out_profit = products_and_clients_per_day[i]
  double_sales = min(2*k, l)
  res += double_sales

for i in range(f, n):
  k, l, sell_out_profit = products_and_clients_per_day[i]
  normal_sales = min(k, l)
  res += normal_sales

print(res)


n , f = list(map(int,input().split()))
total_products = 0
sale_list = []
for i in range(n):
    p , c = list(map(int,input().split()))
    total_products += min(p,c)
    sale_list.append((min(2*p,c),min(p,c)))

sale_list.sort(key = lambda x:x[0]-x[1])
for i in range(f):
    add = sale_list.pop()
    total_products = total_products + add[0] - add[1]

print(total_products)

n, f = input().split()
n , f = int(n), int(f)
arr = [input().split() for i in range(n)]

arr = [(int(dayStrings[0]), int(dayStrings[1])) for dayStrings in arr]

arr = sorted(arr, key=lambda x: min(2*x[0], x[1]) - min(x[0], x[1]), reverse=True)

res = sum(min(2*arr[ind][0], arr[ind][1]) if ind < f else min(arr[ind][0], arr[ind][1]) for ind in range(n))
print(res)





n, f=map (int, input (). split ()) 
days=[] 
ans=0
for i in range (n) :
    k, l=map (int, input (). split ()) 
    if(k<l):
        new_k=2*k
        if new_k>=l:
            days. append (k-l) 
        else:
            days. append (-k) 
        ans+=k
    else:
        ans+=l

days =sorted(days) 

for i in range (min(f, len(days))) :
    ans-=days[i] 
print (ans)     

import sys
read=lambda:sys.stdin.readline().rstrip()
readi=lambda:int(sys.stdin.readline())
writeln=lambda x:sys.stdout.write(str(x)+"\n")
write=lambda x:sys.stdout.write(x)

def getM(k,l):
    if k == 0:
        return 0
    if l >= 2*k:
        return 2*k
    else:
        return l

def getO(k,l):
    if k == 0:
        return 0
    if l >= k:
        return k
    else:
        return l

N,F=list(map(int, read().split()))
days=[]
for i in range(N):
    K,L = list(map(int, read().split()))
    M = getM(K,L)
    O = getO(K,L)
    days.append((M-O,M,O))
days.sort(key=lambda x:x[0])
sm = 0
for i in range(F):
    _, m, _ = days[-1-i]
    sm += m
for i in range(N-F):
    _, _, o = days[-1-F-i]
    sm += o
writeln(sm)









read = lambda: map(int, input().split())
n, f=  read()
p = [tuple(read()) for i in range(n)]
d = [min(2 * k,l) - min(k, l) for k, l in p]
d.sort(reverse = 1)
ans = sum(min(k, l) for k, l in p) + sum(d[:f])
print(ans)

x,y=list(map(int,input().split()))
n=0
d=[0]*x
f=[]
for i in range(x):
	a,b=list(map(int,input().split()))
	if b<a:
		n=n+b
	else:
		n=n+a
	if b>a:
		if a*2<b:
			d[i]=a
		else:
			d[i]=b-a
if d!=f:
	d.sort()
	for i in range(1,y+1):
		n=n+d[-i]
print(n)


import sys

# sys.stdin = open('in', 'r')

n, f = list(map(int, input().split()))

arr = []

ans = 0

for line in sys.stdin:
    k, l = list(map(int, line.split()))
    inc = min(k * 2, l) - k
    ans += min(k, l)
    arr.append(inc)

arr.sort(reverse=True)

for i in range(f):
    if(arr[i] > 0):
        ans += arr[i]

print(ans)