시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

A snail is stuck at the bottom of a well which is of height H. Initially, the snail is at height 0 and it tries to get out. Well, being at the bottom (i.e., height 0) has its upsides. For instance, the snail can’t slide down any further (cannot slide into negative height).

A day is made out of N phases. During each phase, the snail will either try to climb up a certain amount, or rest and slide down a certain amount. The snail knows how much it would move in each phase and this is denoted by Pi. If positive, this means that the snail will travel upwards, if negative, the snail will slide downwards (until height 0), if zero, the snail will maintain its height.

Find out the first day and phase such that the snail reaches a height of H to exit the well.

입력

Your program must read from standard input.

The first line of input contains two positive integers H, denoting the height of the well and N, denoting the number of phases per day.

The next line of input contains N signed integers (separated by spaces) describing the snail’s routine: P0, P1, P2, . . . , PN−1 where Pi denotes the amount the snail travels in phase i.

출력

Your program must print to standard output.

Your program should print one line with two integers, separated by a space.

If the snail can reach the top of the well (i.e. height H) for the first time on the phase P of day D, your output should be D followed by P.

Otherwise, if the snail will always be stuck in the well, your output should be −1 followed by −1.

제한

  • 1 ≤ H ≤ 1012
  • −1012 ≤ Pi ≤ 1012
  • 1 ≤ N ≤ 10 000

예제 입력 1

3 1
1

예제 출력 1

2 0

After phase 0 of day 0, the snail has climbed 1 unit.

After phase 0 of day 1, the snail has climbed 1 unit to a height of 1 + 1 = 2 units.

After phase 0 of day 2, the snail has climbed 1 unit to a height of 1 + 2 = 3 units and exits the well.

예제 입력 2

5 1
-1

예제 출력 2

-1 -1

The snail cannot climb upwards at all, hence, the snail is stuck in the well.

예제 입력 3

5 2
4 -2

예제 출력 3

1 0

After phase 0 of day 0, the snail has climbed 4 units.

After phase 1 of day 0, the snail has slid down 2 units to a height of 2 units.

In phase 0 of day 1, the snail climbs 3 more units, up to a height of 2 + 3 = 5 units, and exits the well.