Background

Translated from NOISG 2018 Prelim A. Snail.

Problem Description

A snail is trapped in a well of height $H$.

The snail keeps trying to climb out of the well. Specifically, in one day the snail goes through $N$ stages. In stage $i$, it climbs $P_i$ meters toward the top of the well (can be negative). When the snail’s height is greater than or equal to the height of the well opening, it leaves the well. When the snail’s height is less than $0$, its height is considered to be $0$.

You are asked to find the earliest time when the snail leaves the well, or report that there is no solution.

Note that both days and stages are 0-indexed, meaning the first stage is actually stage $0$. Also, you may need to use long long to store the input numbers.

Input Format

The first line contains two integers $H, N$. The next line contains $N$ integers, where the $i$-th integer represents $P_i$.

Output Format

Output one line with two integers $D, P$, meaning the snail leaves the well on day $D$ at stage $P$. If it can never leave, output -1 -1.

3 1
1

2 0

5 1
-1

-1 -1

5 2
4 -2

1 0

Hint

Sample #1 Explanation

At stage $0$ on day $0$, it climbs $1$ meter, reaching a total height of $1$ meter.

At stage $0$ on day $1$, it climbs $1$ meter, reaching a total height of $2$ meters.

At stage $0$ on day $2$, it climbs $1$ meter, reaching a total height of $3$ meters, and leaves the well.

Sample #2 Explanation

Clearly, the snail can never leave.

Constraints

For $100\%$ of the testdata: $1 \leq H \leq 10^{12}, -10^{12}\leq P_i\leq 10^{12}, 1\leq N \leq 10^4$.

Translated by ChatGPT 5