Problem Description

Player A and Player B are playing a two-player game. Before the game starts, there is an interval sequence of length $n$: $[l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]$, and a given constant $k$.

Player A moves first. She needs to write down a non-negative integer sequence $a$ such that $a_i\in[l_i,r_i]$.

Next, Player B performs several operations. Each operation is one of the following two types:

• Choose $x\in[1,n]$ and $d\in\{1,-1\}$, add $d$ to $a_x$, with cost $1$.
• Choose $[l,r]\subseteq[1,n]$ and $d\in\{1,-1\}$, add $d$ to $a_i$ for all $i\in[l,r]$, with cost $k$.

When Player B makes all elements in $a$ become $0$, the game ends.

Player A wants to maximize the total cost of operations, while Player B wants to minimize the total cost of operations. You need to compute the final total cost when both players use optimal strategies.

Input Format

The first line contains two positive integers $n,k$, representing the sequence length and the operation cost.

In the next $n$ lines, each line contains two non-negative integers $l_i,r_i$.

Output Format

Output one line with one integer representing the answer.

5 2
4 5
1 6
2 3
1 5
3 6

16

5 3
1 8
4 5
2 3
7 9
8 10

30

15 4
84 102
23 31
1 13
70 82
54 85
39 66
11 83
42 93
52 90
49 89
22 25
103 123
13 43
26 103
103 119

800

Hint

Sample #1 Explanation

Player A can set the sequence to $a=[5,6,2,1,6]$. In this case, it can be proven that the minimum total cost Player B can achieve is $16$.

One possible sequence of operations with total cost $16$ is:

• Choose $x=1$, $d=-1$ and operate $3$ times, cost is $1\times 3=3$. The sequence becomes $[2,6,2,1,6]$.
• Choose $x=2$, $d=-1$ and operate $4$ times, cost is $1\times 4=4$. The sequence becomes $[2,2,2,1,6]$.
• Choose $x=4$, $d=1$ and operate $1$ time, cost is $1$. The sequence becomes $[2,2,2,2,6]$.
• Choose $x=5$, $d=-1$ and operate $4$ times, cost is $1\times 4=4$. The sequence becomes $[2,2,2,2,2]$.
• Choose $l=1$, $r=5$, $d=-1$ and operate $2$ times, cost is $2\times 2=4$. The sequence becomes $[0,0,0,0,0]$.

The total cost is $3+4+1+4+4=16$.

Constraints

For all testdata, $1\le n\le 2\times10^5$, $1\le k\le\min(n,2000)$, $0\le l_i\le r_i\le 10^9$.

This problem uses bundled tests.

• Subtask 1 (10 pts): $n\le 8$, $r_i\le 5$.
• Subtask 2 (15 pts): $n\le 20$.
• Subtask 3 (20 pts): $l_i=r_i$.
• Subtask 4 (15 pts): $k=1$.
• Subtask 5 (15 pts): $k=2$.
• Subtask 6 (25 pts): no special constraints.

Translated by ChatGPT 5