题目描述

机器上有

个需要处理的任务，它们构成了一个序列。

这些任务被标号为

个任务被分成若干批，每批包含相邻的若干任务。

从时刻

s，而完成这批任务所需的时间是各个任务需要时间的总和。

注意，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数

Ci​。

请确定一个分组方案，使得总费用最小。

输入格式

第一行一个整数

第二行一个整数

Ci​。

输出格式

一行，一个整数，表示最小的总费用。

输入输出样例

输入

4

输出

#1复制

153

说明/提示

对于

100%

数据，1≤n≤3×105，1≤s≤28，∣Ti​∣≤28，0≤Ci​≤28。

代码实现：

#include
<iostream>