1Gugulu, a JBer, who was an ACMer one year ago, comes to Shanghai University taking part in the International Collegiate Programming Contest again. However, every time when Gugulu came to Shanghai University, he always got an Iron Medal and would consider this competition JB-like. To release his pain, Gugulu would go to the Shanghai Disneyland Park to have fun in taking the Roller Coaster. Gugulu loves the feeling with high-level blood pressure so much which makes him feel as a happy flappy bird who forgets all the Wrong Answers and Time Limit Exceededs etc. We can regard the path of the Roller Coaster as a list of turning points with different heights which can be represented as an array {a1,a2,a3,…,m} nextra Roller Coaster turning points into the path. You, another JBer, are sure that Gugulu is clever enough to get the highest blood pressure as he can. It is very important for you to calculate the exact numbers to make an appointment with a proper cardiologist in advance to save Gugulu's life. You must solve this problem!Gugulu's blood pressure is becoming out of the control!
1Gugulu, a JBer, who was an ACMer one year ago, comes to Shanghai University taking part in the International Collegiate Programming Contest again. However, every time when Gugulu came to Shanghai University, he always got an Iron Medal and would consider this competition JB-like. To release his pain, Gugulu would go to the Shanghai Disneyland Park to have fun in taking the Roller Coaster. Gugulu loves the feeling with high-level blood pressure so much which makes him feel as a happy flappy bird who forgets all the Wrong Answers and Time Limit Exceededs etc. We can regard the path of the Roller Coaster as a list of turning points with different heights which can be represented as an array {a1,a2,a3,…,an}{a_1, a_2, a_3, …, a_n}{a1,a2,a3,…,an} of size n{n}n, and Gugulu's final blood pressure after the game of the Roller Coaster is counted as the sum of all absolute values of the differences between the n−1{n - 1}n−1 pairs of adjacent array numbers, i.e. ∑i=1n−1∣ai−ai+1∣displaystyle sum_{i=1}^{n-1} left| a_i - a_{i+1} right|i=1∑n−1∣ai−ai+1∣. Gugulu always got Iron Medals and is always getting Iron Medals, which makes him keep taking the Roller Coaster over and over again. However, as playing more games, his threshold on the value of blood pressure which can make himself happy is keeping increasing. As a result, the Roller Coaster of Shanghai Disneyland Park can hardly meet Gugulu's need anymore. Therefore, Gugulu decides to add a set of m extra turning points in any order into this path, however, to consider about the reality on the distance of the original path, he can add at most one turning point into any original position between any two original elements in the array (and at most one in the head, at most one in the tail). Gugulu wants to make his blood pressure as high as possible, and he wants to know how much his blood can reach at most when he has added {1,2,3,…,m}{{1, 2, 3, …, m}}{1,2,3,…,m} nextra Roller Coaster turning points into the path. You, another JBer, are sure that Gugulu is clever enough to get the highest blood pressure as he can. It is very important for you to calculate the exact numbers to make an appointment with a proper cardiologist in advance to save Gugulu's life. You must solve this problem! Gugulu's blood pressure is becoming out of the control!
