Maximizing Total Happiness in Housing Assignment

Welcome to the Housing Happiness problem. In a newly built community, there are \(m\) houses arranged in a row and \(n\) people moving in, where \(1 \leq n \leq m\). The houses are numbered from \(1\) to \(m\) and two houses \(u\) and \(v\) are considered neighbors if \(|u-v|=1\). Each person will be assigned to a distinct house. If two persons are assigned to neighboring houses, then they become neighbors.

For the \(i\)-th person, if he has at least one neighbor (i.e. his assigned house has at least one adjacent occupied house), his happiness will be \(a_i\); otherwise, if he has no neighbor, his happiness will be \(b_i\). As the planner, you are to assign persons to houses so as to maximize the total happiness.

Note about the arrangement: The occupied houses can be partitioned into several contiguous groups. In each group:
- If the group consists of a single person, his happiness is \(b_i\).
- If a group contains two or more persons, every person in that group obtains a happiness of \(a_i\).

There is an arrangement constraint: if you partition the \(n\) persons into \(k\) groups then at least \(n+k-1\) houses are needed. Thus, a valid assignment must satisfy \(n+k-1 \leq m\), i.e. \(k \leq m-n+1\). This constraint might force you to put some persons together even if for some it is better to be isolated. Your task is to decide which persons should be made neighbors (thus receiving \(a_i\)) and which should be isolated (receiving \(b_i\)), in order to maximize the total happiness.

Input and Output Format: See the sections below.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of persons and the number of houses, respectively). It is guaranteed that \(1 \le n \le m\).

Then \(n\) lines follow. The \(i\)-th of these lines contains two integers \(a_i\) and \(b_i\), which denote the happiness of the \(i\)-th person if he has a neighbor and if he is isolated, respectively.

outputFormat

Output a single integer — the maximum possible total happiness. The total happiness is defined as the sum of the individual happiness of all \(n\) persons according to the assignment.

Note: If a person is in a group with at least one other, his contribution is \(a_i\); otherwise, if he is alone, his contribution is \(b_i\).

sample

3 4
10 1
5 6
0 0

16