题目描述

题目译自 JOISC 2019 Day4 T1「ケーキの貼り合わせ / Cake 3」

今天是 IOI 酱的生日，所以她的哥哥 JOI 君给她预定了一个生日蛋糕。虽然他计划买一整个蛋糕，但是他不小心订成了 $N$ 块蛋糕。这 $N$ 块蛋糕编号为 $1\ldots N$，每块蛋糕都有价值和颜色。第 $i$ 块蛋糕的价值为 $V_i$，颜色深度为 $C_i$。

为了做成一整块蛋糕，他决定选择 $M$ 块互不相同的蛋糕，然后将它们按一定顺序排成一个环。整块蛋糕的美观程度定义如下：

$$\sum_{j=1}^M V_{k_j}-\sum_{j=1}^M|C_{k_j}-C_{k_{j+1}}| $$

其中，他选择了编号为 $k_1,\ldots ,k_M$ 的蛋糕（这里令 $k_{M+1}=k_1$）。换句话说，整个蛋糕的美观程度为选择蛋糕的价值和与所有相邻两块蛋糕颜色深度差的绝对值之和的差。JOI 君想要让整块蛋糕尽可能美观。

写一个程序，在给定蛋糕的块数，选择蛋糕的数目和每块蛋糕的价值和颜色深度的情况下，计算 JOI 君做成的蛋糕的最大美观度。

输入格式

从标准输入中读取以下数据：

第一行两个正整数 $N,M$，意义如题目描述；

接下来 $N$ 行，第 $i$ 行两个数 $V_i,C_i$，表示第 $i$ 块蛋糕的价值和颜色深度。

输出格式

输出一行一个整数到标准输出，表示整个蛋糕的最大美观程度。

5 3
2 1
4 2
6 4
8 8
10 16

6

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879

2323231661

数据范围与提示

对于所有数据，$3\le N\le 2\times 10^5,3\le M\le N,1\le V_i,C_i\le 10^9$。

详细子任务及附加条件如下：

• 子任务 $1$（$5$ 分）：$N\le 100$；
• 子任务 $2$（$19$ 分）：$N\le 2\times 10^3$；
• 子任务 $3$（$76$ 分）：无附加限制。