Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P183PROB - ROUND 3B - Kì nghỉ hè của Anna

Nghỉ hè thì có người đi du lịch, có người đi về nhà với gia đình… Anna thì đi làm ở một của hàng.

Cửa hàng có kế hoạch trong n ngày sau. Mỗi quản lý bán hàng biết chính xác rằng trong ngày thứ i-th có ki sản phẩm sẽ được đóng gói để bán và chính xác li khách hàng sẽ đến với cửa hàng ngày hôm đó. Ngoài ra, người quản lý chắc chắn rằng tất cả mọi người đến cửa hàng mua đúng một sản phẩm hoặc rời khỏi cửa hàng mà không mua bất cứ thứ gì. Hơn nữa, do thời hạn sử dụng ngắn của sản phẩm, người quản lý đã thiết lập quy tắc sau: nếu một số sản phẩm còn lại trên kệ vào cuối ngày, sản phẩm đó không được giữ vào ngày hôm sau và được gửi đến bãi rác.

Người quản lý yêu cầu Anna lựa chọn bất kỳ f ngày trong n tiếp theo để bán hàng. Trên mỗi f ngày chọn số lượng sản phẩm đã được đóng gói để bán sẽ được tăng gấp đôi. Vì vậy, nếu ngày i-th cửa hàng lên kế hoạch đóng gói để bán ki sản phẩm và Anna đã chọn ngày này để bán ra, kệ của các cửa hàng sẽ giữ 2ki sản phẩm. Do đó, có cơ hội để bán sản phẩm gấp hai lần.

Nhiệm vụ của Anna là chọn ngày f để tối đa hóa tổng số sản phẩm bán ra. Cô ấy yêu cầu bạn giúp cô ấy với một vấn đề khó khăn như vậy.

Input

Dòng đầu tiên chứa hai số nguyên n và f (1 ≤ n ≤ 105, 0 ≤ f ≤ n) là số ngày trong kế hoạch của cửa hàng và số ngày mà Anna phải chọn để bán hết.

Mỗi dòng trong số n dòng kế tiếp bao gồm hai số nguyên ki, li (0 ≤ ki, li ≤ 109) là số lượng sản phẩm trên kệ hàng của cửa hàng vào ngày i-th và số lượng khách hàng sẽ đến cửa hàng vào ngày i-th.

Output

In một số nguyên thể hiện số lượng tối đa của sản phẩm mà cửa hàng có thể bán.

Example

Test 1:
Input:
4 2
2 1
3 5
2 3
1 5 Output: 10
Test 2:
Input:
4 1
0 2
0 3
3 5
0 6
Output:
5
Giải thích:
Trong ví test đầu tiên chúng ta có thể chọn ngày với số 2 và số 4 để bán ra. Trong trường hợp này, số lượng sản phẩm mới được bán sẽ tương ứng với [2, 6, 2, 2]. Vì vậy, vào ngày đầu tiên cửa hàng sẽ bán 1 sản phẩm, thứ hai - 5, vào ngày thứ ba - 2, vào ngày thứ tư - 2. Tổng cộng 1 + 5 + 2 + 2 = 10 đơn vị sản phẩm.
Trong ví dụ thứ hai, bạn có thể bán 5 sản phẩm, nếu bạn chọn ngày thứ ba để bán ra.

Được gửi lên bởi:adm
Ngày:2018-03-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.