메뉴 건너뛰기

문제

00c27 다리 건너기 실험 1  

시간메모리제출 올바른 답 비율
1초64MB
102
17
16.7%


나의 횟수나의 최근 판정시도 성공 비율
2216
72.7%
다리 건너기 실험  

열차가 지나는 다리를 건설하는 충북건설회사는 최근에 자신들이 건설한 다리의 견고함을 확인하고자 다리 위로 KTX 열차가 지나는 실험을 하고자 한다. 다리의 길이는 40m이고, KTX 열차의 각 칸은 10m, 각 칸의 무게는 서로 다르다. 열차가 다리를 건너게 되면 열차의 4칸이 다리를 지나게 되고, 편의상 다리의 경계선에서 1개 칸이 걸치는 경우는 없다고 가정한다. 그런데, 다리 위에 있는 칸들의 무게의 총합이 다리가 견딜 수 있는 무게보다 더 무거우면 다리가 무너지게 된다. 충북건설회사는 이 실험을 통해 자신들이 건설한 다리를 무사히 건널 수 있는 KTX 열차의 칸 수를 결정하여 철도청에 통보하려고 한다.

다리가 견딜 수 있는 무게와 KTX 열차의 각 칸의 무게가 주어질 때 다리를 건널 수 있는 열차의 최대 칸 수를 계산하는 프로그램을 작성하시오.

입력

입력 파일의 첫 번째 줄에 다리가 견딜 수 있는 최대무게 W(1<=W<=100000)가 주어진다. 두 번째 줄에 열차의 칸 수 N(1<=N<=100000)이 주어진다. 그 다음 N개의 줄에 각 칸의 무게 wi가(1<=i<=N, 1<=wi<=100000) 순서대로 주어진다. 따라서, KTX 열차의 각 칸의 순서를 임의로 변경할 수 없으며 항상 1번째 칸부터 i번째(1<=i<=N) 칸까지 다리를 건널 수 있다.

출력

첫 번째 줄에 다리를 건널 수 있는 최대 칸 수를 출력한다.

※ 예시 1 : 처음 4칸의 총 무게는 50+30+10+10=100이므로 다리가 견딜 수 있다. 처음 한 칸이 다리를 완전히 건너면 다리 위에는 그 다음 4칸이 놓여 있게 되고 총 무게는 30+10+10++40=90이므로 다리가 견디기에 충분하다. 그러나 열차의 마지막 4칸이 다리 위에 놓이게 되면 다리가 무너진다. 왜냐하면 10+10+40+50=110이고 이 무게는 다리가 견딜 수 없기 때문이다. 따라서 충북건설회사는 철도청에게 ‘처음 5개의 칸만 다리를 건널 수 있기 때문에, 6번째 칸 앞에서 열차를 분리해야 한다’고 통보하였다.

※ 예시 2 : 열차의 첫 번째 칸의 무게가 150으로 다리가 바로 무너지기 때문에 열차의 어떠한 칸들도 다리를 건널 수 없다. 충북건설회사는 철도청에 ‘이 열차는 첫 번째 칸이 너무 무거워서 어떠한 칸도 다리를 건널 수 없다’고 통보하였다(KTX 열차의 각 칸의 순서를 변경할 수 없음을 유념하라).

예시
1입력
100
6
50
30
10
10
40
50
출력
5
2입력
100
3
150
1
1
출력
0
위로