题号：NC273396
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Dodo, who reincarnated into the magical world, is managing a superpower orchard. The energy of this superpower orchard is generated by the process of merging fruits. Now, all the fruits have been picked by and arranged in a row.
Specifically, each fruit has two energy attributes,
and 
. Considering two adjacent fruits with the left one denoted as )
and the right one as )
, merging them can release energy 
and produce a new fruit )
.
Dodo hired a magician to multiply the initial energy attributes and of a contiguous interval (at least one) of fruits by 
. Then, pairs of adjacent fruits are chosen for merging until only one fruit remains.
Dodo wants to maximize the energy released by merging all the fruits. Please help Dodo calculate the maximum amount of energy that can be released.
Specifically, each fruit has two energy attributes,
Dodo hired a magician to multiply the initial energy attributes
Dodo wants to maximize the energy released by merging all the fruits. Please help Dodo calculate the maximum amount of energy that can be released.
输入描述:
The first line consists of two integers, indicating the total number of fruits and the integer k by which the magician can multiply a contiguous interval of fruits. Please note that k may be negative.
The followinglines each contain two integers
, representing the two attributes of the
-th fruit from left to right. Please note that attributes may be negative.
输出描述:
One line with a single integer representing the answer.
示例2
备注:
，