Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

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ó k_i sản phẩm sẽ được đóng gói để bán và chính xác l_i 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 k_i 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ữ 2k_i 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 ≤ 10⁵, 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 k_i, l_i (0 ≤ k_i, l_i ≤ 10⁹) 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.