蛋糕拼接 3

题号：NC53276
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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

今天是IOI酱的生日，所以她的哥哥JOI君给她预定了一个生日蛋糕。虽然他计划买一整个蛋糕，但是他不小心订成了N块蛋糕。这N块蛋糕编号为 $1 \ldots N$ ，每块蛋糕都有价值和颜色。第i块蛋糕的价值为 $V_i$ ，颜色深度为 $C_i$ 。
为了做成一整块蛋糕，他决定选择M块互不相同的蛋糕，然后将它们按一定顺序排成一个环。整块蛋糕的美观程度定义如下：
$\sum_{j=1}^MV_{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行两个数，表示第i块蛋糕的价值和颜色深度。

输出描述:

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

示例1

输入

复制

输出

复制

说明

如果JOI君选择1,3,2号蛋糕并按这个顺序排列，这些蛋糕的权值和为2+6+4=12，相邻两块蛋糕颜色深度差的绝对值之和为|1-4|+|4-2|+|2-1|=6。因此，整个蛋糕的美观度为12-6=6。
他也可以选择2,3,4号蛋糕并按这个顺序排列，得到的蛋糕美观程度也是6。
因为他不能做成一块美观程度大于6的蛋糕，所以输出6。

示例2

输入

复制

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

输出

复制

2323231661

备注:

对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3039