Noora quyết định đi làm thêm mùa hè này tại một cửa hàng. Cửa hàng có kế hoạch cho \(n\) ngày tới. Mỗi ngày, quản lý bán hàng biết chính xác rằng sẽ có \(k_i\) sản phẩm được bán và \(l_i\) khách hàng đến cửa hàng. Mỗi khách hàng sẽ mua một sản phẩm hoặc rời đi nếu hết hàng. Do thời hạn sử dụng ngắn, những sản phẩm không bán được trong ngày sẽ bị loại bỏ và không được bán vào những ngày sau đó.

Quản lý quyết định tổ chức khuyến mại, cho phép Noora chọn \(f\) ngày để tăng gấp đôi sản phẩm bán ra. Nhiệm vụ của Noora là chọn \(f\) ngày để tối đa hóa tổng số sản phẩm bán được.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(f\) (\(1 \leq n \leq 10^5, 0 \leq f \leq n\)) cho biết số ngày và số ngày khuyến mại.
• Mỗi dòng tiếp theo chứa hai số nguyên \(k_i\) và \(l_i\) (\(0 \leq k_i, l_i \leq 10^9\)) cho biết số sản phẩm và số khách hàng trong ngày \(i\).

Output

• In ra một số nguyên là số lượng sản phẩm tối đa có thể bán được.

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n \leq 20\).
• Subtask 2 (\(30\%\) số điểm): \(k = 1\).
• Subtaks 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ

4 2
2 1
3 5
2 3
1 5

10

4 1
0 2
0 3
3 5
0 6

5