Responsive image

问题 1140 --阿凡提过河

1140: 阿凡提过河

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

阿凡提戴着一群羊要过河，河上只有一条船可以到对岸，阿凡提若要自己过河，需要m分钟，现在阿凡提带了N只羊，若想每次带i只羊过河，需要比带i-1只羊过河多耗费mi的时间，请你算出阿凡提要怎么过河才能使花费的时间最小。（带一只羊过河需要m+m1的时间，带2只羊需要m+m1+m2）

输入描述

第一行输入k,代表k组测试数据。

第二行输入n和m,(1 ≤ N ≤ 1000 , 1≤ M ≤ 500).

剩余n行输入mi, (1 ≤ Mi ≤ 1000)

输出描述

对每组测试数据，求出阿凡提过河需要的最少时间。

样例输入

2    
2 10   
3
5
5 10  
3
4
6
100
1

样例输出

18
50

来源

王广威 

[提交][状态]
ACM算法攻关部