1241 - Cube Tower 1

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 51

Solved: 16

Description
There are a large cube tower which are stacked as following:
  • There are N levels, numbered 0, 1, 2, ……,N-1 from bottom to top, each has (N-i)*(N-i) cubes.

  • Each level’s topmost row and leftmost column are against walls.


It is known that there is a value assigned to each cube. All cubes on the same level have a same value. You will be given the values V[i] of the cubes on each level and a number M. Find the cuboid with x*y*z cubes (1 <= x*y*z <= M , SIZE OF CUBOID CAN NOT BE 0), with the maximum total value possible. And calculate the maximum total value.
Input
The first line contains a single integer T, the number of test cases.
For each case:
The first line contains two integers N (1<=N<=1,000), M (1<=M<=1,000,000,000) indicating the levels and the maximum number of cubes you can get.
The second line contains N number of V[i],refer to the description (i=0,1,2,……N-1, -10000<=V[i]<=10,000).
Output
For each case, output a single integer, indicating the maximum total value.
sample input
3
2 2
2 4
6 5
3 -2 2 1 -3 1
6 50
7 3 -2 -5 1 4
sample output
6
15
252
hint
source
<a href="http://www.gaewah.com/">Gaewah</a>
© 2015 HUST ACMICPC TEAM. All Right Reserved.