Summer sell-off

题意翻译

## 题目描述 商店在n天中出售商品。对于第i天，出售ki件商品，会有有li个顾客购买商品。每个顾客买且只买一件商品。 商店的老板会选择f天。在这f天中，每天出售的商品数量为原来出售商品数量的两倍。老板想知道，如何选择这f天，能使出售的商品最多 ## 输入格式 第一行两个整数n和f(1<=n<=10^5,0<=f<=n)。 接下来的n行，每行两个整数ki和li(0<=ki,li<=10^9 )，表示每天出售的商品数量和顾客人数。 ## 输出格式 一行一个整数，表示商店在选择f天后，可销售产品的最大数量。 ## 输入输出样例 无

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4 2
2 1
3 5
2 3
1 5

输出样例 #1

10

输入样例 #2

4 1
0 2
0 3
3 5
0 6

输出样例 #2

5

说明

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.