珂神的球

Time Limit: 20000 ms

Memory Limit: 65535 ms

Description

有一些玻璃球,每个玻璃球有一定的价值,有一个高度为m的楼,用这些玻璃球测出在哪一层把玻璃球扔下去的时候正好玻璃球能摔坏.每次扔一个求,不管有没有摔坏,花费的代价是k,如果球摔坏的话,那么要花费额外的代价ki(第i个球的价值).现在要求出在最坏情况下正好摔坏球的那个楼层,并且保证总的花费最小.(保证最高楼层一定会把球摔坏)

Input

第一行输入一个整数 x (x<=100)表示有x个case 每个case第一行三个正整数 n , m , k (n<=50,m<=1000,k<=100)分别表示有n个球,m层楼,还有上文中提到的k 第二行有n个数,表示每个球的代价(ki<=100)

Output

一个数,最小的代价

Sample Input

2
2 4 2
1 1
5 10 3
1 2 3 4 5

Sample Output

7
13

Hint

Source


提交代码