The Karting championship will be held on a straight road. There are N keypoints on the road. The path between keypoint i and i+1 has a degree of difficulty Di(Di may be negative if the path is too smooth). Now the Organizers want to darw up some routes among these keypoints(The number of routes can be many to avoid a boring match). The organizers will choose some checkpoints from the keypoints for the routes(Each route shold include at least two checkpoints, and each keypoint can not be chosen as checkpoint more than once. Two routes can not share one checkpoint). The players should drive their karts to pass the checkpoints in the given order and return to the first checkpoint.
For example, if there are 4 checkpoints 1,3,2,4 in order in a route, players shold drive pass keypoint 1,2,3,2,3,4,3,2,1 in order. In this example, the players should make a 180 degree turn 4 times in the route(When players return to checkpoint 1, they also need to make a 180 degree turn). Makeing a 180 degree turn also has a degree of difficulty D0. The difficulty of a route is defined as follow. The initial difficluty is 0. Each time the players in the route need to pass the path between keypoint i and i+1, the difficulty shold increase Di, and each time the players need to make a 180 degree turn, the difficulty should increase D0.
To make the championship more exciting, the organizers want to maximize the sum of difficulty of all routes. They will choose exactly M keypoints to set up checkpoints. So what is the maximum sum of difficulty of all routes?