Xsquare And Coin Collection
Practice
3.4 (29 votes)
Ad Hoc
Approved
Easy
Implementation
Open
Problem
70% Success 15535 Attempts 20 Points 3s Time Limit 256MB Memory 1024 KB Max Code

Xsquare loves to play with the coins very much. Today , he has N stacks of coins . Each stack of coins has some non zero height Hi equal to the number of coins on that stack ( considering all the coins are identical and each coin has a height of 1 unit ) .

In one move, Xsquare can select any number of consecutive stacks of coins such that the height of each selected stack of coins Hi ≤ K . Once such a sequence of stacks is chosen , Xsquare can collect any number of coins from the chosen sequence of stacks .

Xsquare wonders what is the maximum number of coins that he can collect this way ?

INPUT

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 K where N being the number of stacks of coins. Second line of each test case contains N space separated integers denoting the number of coins Hi on each stack .

OUTPUT

For each test case , Print the maximum number of coins Xsquare can collect following the above gaming strategy.

CONSTRAINTS

1 ≤ T ≤ 105

1 ≤ N ≤ 105

1 ≤ K ≤ 109

1 ≤ Hi ≤ 109

Note :

sum of N over all the test case will not exceed 106.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
9 votes
Tags:
Real worldIntroduction to Dynamic Programming 1AlgorithmsDynamic Programming
Points:30
9 votes
Tags:
Depth First SearchEasyGraphsImplementationRecursion
Points:20
21 votes
Tags:
ApprovedBrute-force searchData StructuresDynamic ProgrammingEasyOpen