You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

本题译自 CCO 2015 Day1 T1「Hungry Fox」

到你的宠物狐狸的晚餐时间啦！他的晚餐包含 $N$ 块饼干，第 $i$ 块饼干的温度是 $T_i$ 摄氏度。同时，在晚餐中还包含了一大盘 $W$ 摄氏度的水。

在喝了一口水之后，你的狐狸开始吃饭了。每当他吃一块饼干时，这块饼干的美味度为当前饼干与吃/喝的前一样食物（包括饼干和水）的温度的差的绝对值。它可以在任意时间喝水（保证水喝不完），或按任意顺序吃饼干。

最后狐狸获得的美味值为它吃下的每块饼干的美味度之和。请求出狐狸获得的最小和最大的美味值。

输入格式

第一行两个整数 $N,W$，表示饼干总数和水的温度。

接下来 $N$ 行，每行一个整数 $T_i(1\le i\le N)$ 表示第 $i$ 块饼干的温度。

输出格式

输出两个整数，分别为狐狸获得的最小和最大的美味值。

3 20
18
25
18

7 16

提示

要得到最小美味值，一种可行的方案是，狐狸先喝水，然后吃第一块饼干，再吃第三块饼干，接着喝水，最后吃下第二块饼干，这样做，它所感受到的温度分别为 $20,18,18,20,25$ 摄氏度，总的美味度为 $2+0+5=7$。

要得到最大美味值，一种可行的方案是，狐狸先喝水，然后按顺序吃饼干，它所感受到的温度分别为 $20,18,25,18$ 摄氏度，总的美味度为 $2+7+7=16$。

对于 $30\%$ 及以上的数据， $W=0$；

对于 $100\%$ 的数据， $1\le N \le 100000, 0\le W \le 10^9, 0 \le T _ i \le 10 ^ 9$。