AT_scpc2026_div1_k Storing Roll Cake

#### 表示言語 / / Coshaman bought a roll cake of length $ L $ for the SCSC clubroom. The roll cake consists of $ L $ consecutive pieces of length $ 1 $ , and the preference value of the $ i $ -th piece from the left is $ V_i $ . Lulu wants to store the roll cake in a refrigerator. However, the clubroom refrigerator cannot store a roll cake of length greater than $ K $ , so Lulu decided to cut the roll cake into pieces of length at most $ K $ . Since cutting through a piece would make it ugly, Lulu must cut only between adjacent pieces. When a roll cake is put into the refrigerator, only the end piece is visible from outside. Since the roll cakes must be put in with a fixed orientation, only the rightmost piece of each cut roll cake is visible. Lulu likes pretty things, so Lulu defines the beauty of storage as the sum of the preference values of the visible pieces. Cutting a roll cake is hard work, so Lulu wants to store it with large beauty of storage while using little effort. When cutting a roll cake of length $ s $ into two roll cakes of lengths $ x $ and $ y $ ( $ x+y=s $ ), the required effort is $ x \times y $ . If several cuts are made, the effort required for the storage is the sum of the effort required for each cut. Given $ L $ , $ K $ , and the preference values of each roll cake piece, find the maximum possible value of $ (\text{beauty of storage}) - (\text{effort required for storage}) $ .

The input is given from Standard Input in the following format: > $ L $ $ K $ $ V_1 $ $ V_2 $ $ \dots $ $ V_L $

Output the maximum possible value of $ (\text{beauty of storage}) - (\text{effort required for storage}) $ .

### Constraints - $ 1 \leq K \leq L \leq 1\,000\,000 $ - $ 0 \leq V_i \leq 10^9 $ - All given numbers are integers.