[Solution] ATM and Students solution codeforces

ATM and Students solution codeforces

Polycarp started working at a bank. He was assigned to monitor the ATM. The ATM initially contains 𝑠s rubles.

A queue of 𝑛n students lined up to him. Each student wants to either withdraw a certain amount of money or deposit it into an account. If 𝑎𝑖ai is positive, then the student credits that amount of money via ATM. Otherwise, the student withdraws |𝑎𝑖||ai| rubles.

In the beginning, the ATM is turned off and an arbitrary number of students are not served. At some point, Polycarp turns on the ATM, which has an initial amount of 𝑠s rubles. Then, the remaining students start queueing at the ATM. If at some point in time there is less money in the ATM than the student wants to withdraw, then the student is not served and Polycarp turns off the ATM and does not turn it on anymore.

More formally, the students that are served are forming a contiguous subsequence.

Also read: Make Even solution codeforces

Polycarp wants the ATM to serve the maximum number of students. Help him in this matter. Print the numbers of the first and last student, or determine that he will not be able to serve anyone.

In other words, find such a longest continuous segment of students that, starting with the sum of 𝑠s at the ATM, all these students will be served. ATM serves students consistently (i.e. one after another in the order of the queue).

Input ATM and Students solution codeforces

The first line of the input contains one integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

Each test case consists of two lines. The first one contains integers 𝑛n and 𝑠s (1𝑛21051≤n≤2⋅1050𝑠1090≤s≤109) — the length of the 𝑎a array and the initial amount of rubles in the ATM. The second contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (109𝑎𝑖109−109≤ai≤109) — elements of the 𝑎a array. Note that 𝑎𝑖ai can be zero.

It is guaranteed that the sum of the values 𝑛n over all test cases does not exceed 21052⋅105.

Output ATM and Students solution codeforces

Print 𝑡t lines, each line must contain the answer to the corresponding set of input data: if the answer exists, print the numbers of the first and last served student. If there is no solution, then print -1 on the line.

If there are several possible answers, print any.

Example ATM and Students solution codeforces

input

Copy
3
4 10
-16 2 -6 8
3 1000
-100000 -100000 -100000
6 0
2 6 -164 1 -1 -6543

output

Copy
2 4
-1
1 2
Note ATM and Students solution codeforces

In the first test case, the only correct answer is 2 4, since when serving students, the number of rubles at the ATM does not become negative, and this is the maximum number of students that can be served.

In the second test case, the answer is -1, as there is not enough money for any student at the ATM.

In the third test case, the answer can be either 1 2 or 4 5.

ATM and Students solution codeforcesMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcode

Leave a Comment

Your email address will not be published. Required fields are marked *