Minimum Cost Production of Optical Discs

You are given n days and you need to produce k complete optical discs. Each disc must go through two sequential processes: first, it is pressed at factory A and then coated with a reflective layer at factory B. The processing cost is different on each day. Specifically, on day i (1-indexed), factory A processes one disc at a cost of a_i and factory B processes one disc at a cost of b_i.

Every day you have two opportunities (in order):

1. You may send a disc to factory A (or choose not to). This operation costs a_i if performed and increases the number of discs that have completed the first process but are waiting for the second.
2. You may send a disc that has already been processed by factory A to factory B (or choose not to). This operation costs b_i if performed and completes the disc. Note that if you perform the first operation on the same day, immediately after that the disc processed on that day is also available for processing by factory B in the same day.

Each factory can process at most one disc per day. Discs that are pending (i.e. processed by A but not yet by B) can be stored at no extra cost and can be processed in later days as long as the schedule permits (i.e. a disc must be processed by A before being processed by B).

Your task is to compute the minimum total cost required to produce k fully processed discs under these constraints.

Formally, if you denote the processing cost on day i as
\(a_i\) for factory A and \(b_i\) for factory B, and if a disc is processed by factory A on day i and by factory B on day j (with \(i \le j\)), the cost for that disc is \(a_i + b_j\). Note that if both operations are done on the same day, its cost is \(a_i + b_i\).

You are allowed to perform at most one A operation and one B operation each day. Determine the minimum total cost to produce exactly k discs.

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n), representing the number of days available and the number of complete discs to produce.

Each of the following n lines contains two integers a_i and b_i (cost for processing a disc at factory A and factory B on day i, respectively).

outputFormat

Output a single integer, the minimum total cost to produce k complete optical discs.

sample

3 2
3 5
4 1
2 3

9