Informatica Online Judge

  해양탐사선 GSHS호 [0473 / 01D9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 80   Total Tried : 409


The Champion of this Problem (C++) : gs19022 - 0ms / 265byte
My Best Submission (C++) : N/A

[]

Background

이번에 GSHS의 셈틀에서 해양탐사선 GSHS호를 개발하였다.





이 해양탐사선은 이번에 심해에서 발견된 새로운 미생물을 채쥐할 목적으로 만들어졌다. 이 미생물의 특징은 아주 깊은 심해에서만 활동하며, 시간대 별로 채집할 수 있는 개체수가 달라지는 것이 특징이다.

GSHS호는 m시간을 연속해서 작업할 수 있는 배터리를 장착하고 있다. 그리고 GSHS호가 쉬는 동안에는 자체적으로 배터리를 충전할 수 있는 시스템을 가지고 있다. 만약 1시간을 쉰다면 1시간을 사용할수 있는 배터리 량을 충전할 수 있다는 의미이다.

만약 3시간을 연속해서 작업할 수 있는 배터리를 장착했다면 2시간을 일하고 1시간을 쉬면 다시 2시간을 일할 수 있다.

시간 별 미생물 개체수가 주어질 때, 채취할 수 있는 미생물의 최대 량을 구하는 프로그램을 작성하시오.

Input

첫 째줄에 연속해서 일할 수 있는 시간 h와 배터리용량 m이 공백으로 구분되어 입력된다.
다음 줄부터 h줄에 걸쳐서 시간대별 개체수 pi가 주어진다.
(1<=h<=10,000, 1<=m<=1,000, 1<=pi<=1,000)

Output

위 조건으로 얻을 수 있는 최대 개체수를 출력한다.

IO Example

입력
3 1
100
76
84

출력
184

입력2
8 2
1
8
2
7
3
6
4
5

출력2
27


1번의 설명 : 배터리 용량이 1시간이 이므로 첫째 시간에 일하고 100을 얻고 1시간 충전하고(76는 버림) 다음 1시간 동안 일해서 84를 얻어 합계 184를 채취하는 것이 최대이다.
즉, 간단히 나타내면 (100) 76 (84)으로 나타낼 수 있다.

2번 설명 : (1 8) 2 (7) 3 (6) 4 (5)
처음 2시간 연속으로 일하고, 한 시간 충전하고, 한 시간 일하고를 반복하면 최대값인 27을 얻을 수 있다.

출제 - 정종광 2/2(Informatics Teacher)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]