P17205 "DLESS-6" Tnemerced Tnemercni

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.

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 one line with one integer representing the answer.

**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