Solar holidays! Someone is going on trips, some other is visiting grandparents, but some other person is trying to get a part-time job. This summer MURPH decided that she wants to earn some money, and took a job in a shop as an assistant for the money.
Shop, where MURPH is working, has a plan on the following n days. For each day sales manager knows exactly, that in i-th day qi products will be put up for sale and exactly wi clients will come to the shop that day. but, his manager is sure, that everyone, who comes to the shop for sell out, buys exactly one product or, if there aren't any left, leaves the shop without buying anything at all. also, due to the short shelf-life of the products, manager given the following rule: if some part of the products left on the shelves at the day end , then those products are not kept on the next day and are sent to the trash straightaway.
For advertising purposes manager offered to start a sell-out in the shop. He asked MURPH to choose any P days from n next for sell-outs. On each of P 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 qi products and MURPH has chosen this day for sell-out, shelves of the shop would keep 2·qi products. Consequently, there is an opportunity to sell two times more products on days of sell-out.
MURPH's task is to choose P 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 P denoting the number of days in shop's plan and the number of days that MURPH has to choose for sell-out.
Each line following after this contains n subsequent lines contains two integers qi, wi which denotes 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 that gives the maximum number of products that shop can really sell .
CONSTRAINTS :
- 1 ≤ n ≤ 10^5
- 0 ≤ P ≤ n
- 0 ≤ qi, wi ≤ 10^9
we can choose days with numbers 2 and 4 for sell. Now In this case new numbers of products for sale would be equal to [2, 6, 2, 2] . on this same day one shop will sell 1 product, on the day 2 — 5, on the day 3 — 2, on the day 4 — 2. In total 1 + 5 + 2 + 2 = 10 product units.
