0

Bird and maximum fruit-gathering

Difficulty: EASY
Avg. time to solve
20 min
Success Rate
80%

Problem Statement
Suggest Edit

There are ‘N’ trees in a circle. Each tree has a fruit value associated with it. A ninja bird eyeing the fruits on the tree is blazingly fast. It can sit on a tree for 0.5 sec to gather all the fruits present on the tree no matter the number of fruits present in the tree and then the ninja bird can move to a neighbouring tree. It takes the ninja bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she can’t pick any more fruits from that tree. The maximum number of fruits she can gather is infinite. You are given N and M (the total number of seconds the ninja bird has), and the fruit values of the trees. Your task is to maximize the total fruit value that the ninja bird can gather. The bird can start from any tree.

Note
All trees are in a circle
For Example
Input: N=7 M=3
arr[] = { 2 ,1 ,3 ,5 ,0 ,1 ,4 }

Output: 9

Explanation: 
She can start from tree 1 and move to tree 2 and then to tree 3.
Hence, total number of gathered fruits = 1 + 3 + 5 = 9.
Input Format
The first line of input contains a single integer ‘T’ denoting the number of test-cases for the problem.
The first line of each test case in the input contains two space-separated integers ‘N’ and ‘M’ denoting the number of trees and the seconds given to collect the fruits from the trees.


And the second line contains single space-separated integers, denoting the fruits on each tree.
Output Format :
return the maximum number of fruits the ninja bird can gather in the given amount of time.

Note: You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= M <= 5000
1 <= N <= 5000
1 <= ARR[i] <= 5000


Time Limit: 1 sec
Sample Input 1 :
2
6 2
1 6 2 5 3 4
7 3
2 1 3 5 0 1 4 
Sample Output 1:
8
9

Explanation for Sample 1:

She can start from tree 1 and move to tree 2. In this case, she will gather 6 + 2 = 8 fruits. She can also start from tree 3 and move to tree 4. In this case, too, she will gather 5 + 3 = 8 fruits. Therefore the answer here is 8.

She can start from tree 1 and move to tree 
2 and then to tree 3. Hence, the total number of gathered fruits = 1 + 3 + 5 = 9.
Sample Input 2 :
1
8 3
2 3 4 1 2 1 5 3
Sample Output 2 :
10
Want to solve this problem? Login now to get access to solve the problems