All Tracks Basic Programming Implementation Basics of Implementation Problem

Surojit with Balls
No tags

Surojit is an awesome cricketer of JGEC. His passion for the game & his talents are well known to everyone. Now he has a very weird hobby. He collects all the balls in each of the matches he has played and stores them in cylindrical containers one ball on top of other, thus forming a “stack” of balls.

So, he has many such stack of balls kept in his room. Each stack has height Hi , denoting the number of balls in that particular stack. One fine day, Surojit decides to play a small game. This game consists of many number of rounds. In each round, he can select any number of consecutive stack of balls, such that number of balls selected is maximum. But wait, there’s a catch! The height of the stacks must be at most M. Now help Surojit to select maximum number of balls. You have the liberty to play any number of rounds.

First line of input contains a single integer T denoting the number of test cases. First line of each test case contains two space separated integers N and M where N being the number of stacks of balls. Second line of each test case contains N space separated integers denoting the number of balls Hi on each stack.

For each test case , print the maximum number of balls Surojit can collect following the above gaming strategy in a new line.


  • 1 ≤ T ≤ 105
  • 1 ≤ N ≤ 105
  • 1 ≤ M ≤ 109
  • 1 ≤ Hi ≤ 109

7 2
4 2 3 5 1 1 1
8 2
6 2 2 3 1 1 1 5
Time Limit: 1.0 sec(s) for all input files combined.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications