다리를 건너는 기차

면접 대비

시간 제한1초메모리 제한128 MB

요약

다리 위에 동시에 최대 4량이 있을 수 있을 때, 연속한 4량의 무게 합이 제한을 넘지 않도록 건널 수 있는 가장 긴 접두사를 구한다.

난이도: 보통10점 중 4점
유형: 슬라이딩 윈도우, 배열, 구현, 누적 합
정답자: 아직 제출이 없습니다

문제

각 칸의 길이가 10m인 화물열차가 다리를 건너려고 한다. 각 칸의 무게는 서로 다를 수 있다. 다리의 길이는 40m이므로 한 번에 최대 4칸까지 다리 위에 올라갈 수 있다. 어느 순간이든 다리 위에 있는 칸들의 무게 합이 정해진 한계 무게를 초과하면 다리가 무너진다. 칸에는 1번부터 $N$ 번까지 번호가 매겨져 있으며, 이 순서대로 다리를 건넌다 (즉 1번 바로 뒤에 2번, 그 바로 뒤에 3번, …).

1번부터 $T$ 번까지의 칸을 순서대로 다리를 건너게 할 수 있는 가장 큰 $T$ 를 구하여라.

입력

첫째 줄에 다리가 한 번에 감당할 수 있는 최대 무게 $W$ ( $1 \le W \le 100000$ )가 주어진다. 둘째 줄에 옮기려는 화물칸의 수 $N$ ( $1 \le N \le 100000$ )이 주어진다. 다음 $N$ 개의 줄에는 각각 $i$ 번째 칸의 무게를 나타내는 양의 정수 $w_i$ ( $1 \le w_i \le 100000$ )가 주어진다.

출력

주어진 순서대로 다리를 건널 수 있는 화물칸의 최대 개수를 나타내는 음이 아닌 정수를 출력한다.

힌트

예를 들어 다리가 100까지 견딜 수 있고 칸들의 무게가 차례로 50, 30, 10, 10, 40, 50이라고 하자. 처음 네 칸의 무게 합은 $50 + 30 + 10 + 10 = 100$ 으로 한계를 넘지 않는다. 첫 칸이 빠지고 다섯 번째 칸이 올라오면 $30 + 10 + 10 + 40 = 90$ 으로 역시 넘지 않는다. 그러나 마지막 네 칸은 $10 + 10 + 40 + 50 = 110$ 으로 한계를 넘어 다리가 무너진다. 따라서 처음 5칸만 다리를 건널 수 있다.

예제3

예제 1
입력
```
100
6
50
30
10
10
40
50
```
예상 출력
```
5
```
예제 2
입력
```
100
1
100
```
예상 출력
```
1
```
예제 3
입력
```
5
1
10
```
예상 출력
```
0
```