NC53276. 蛋糕拼接 3
描述
题目译自 JOISC 2019 Day4 T1「ケーキの貼り合わせ / Cake 3」
今天是IOI酱的生日，所以她的哥哥JOI君给她预定了一个生日蛋糕。虽然他计划买一整个蛋糕，但是他不小心订成了N块蛋糕。这N块蛋糕编号为
，每块蛋糕都有价值和颜色。第i块蛋糕的价值为
，颜色深度为
。
为了做成一整块蛋糕，他决定选择M块互不相同的蛋糕，然后将它们按一定顺序排成一个环。整块蛋糕的美观程度定义如下：
其中，他选择了编号为
的蛋糕（这里令
）。换句话说，整个蛋糕的美观程度为选择蛋糕的价值和与所有相邻两块蛋糕颜色深度差的绝对值之和的差。JOI君想要让整块蛋糕尽可能美观。
写一个程序，在给定蛋糕的块数，选择蛋糕的数目和每块蛋糕的价值和颜色深度的情况下，计算JOI君做成的蛋糕的最大美观度。
为了做成一整块蛋糕，他决定选择M块互不相同的蛋糕，然后将它们按一定顺序排成一个环。整块蛋糕的美观程度定义如下：
其中，他选择了编号为
写一个程序，在给定蛋糕的块数，选择蛋糕的数目和每块蛋糕的价值和颜色深度的情况下，计算JOI君做成的蛋糕的最大美观度。
输入描述
从标准输入中读取以下数据：
第一行两个正整数N,M，意义如题目描述；
接下来N行，第i行两个数，表示第i块蛋糕的价值和颜色深度。
输出描述
输出一行一个整数到标准输出，表示整个蛋糕的最大美观程度。
示例1
输入:
5 3 2 1 4 2 6 4 8 8 10 16
输出:
6
说明:
如果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