책상 위에 n개의 사탕이 일렬로 놓여 있다.

각 사탕은 '당도'라는 수치가 있어, 왼쪽에서 i번째 사탕의 당도는 a_i이다.

준혁이는 이 n개의 사탕 중 몇 개의 사탕을 먹기로 결심했다.

준혁이는 먹는 사탕들의 당도의 총합을 최대화하고싶다.

그러나, 너무 많은 사탕을 먹는 것은 치아 건강에 좋지 않기에,

준혁이는 연속하여 놓여 있는 두 사탕을 동시에 먹지는 않기로 하였다.

준혁이는 자신이 먹을 사탕의 수를 아직 정하지 못했기 때문에, 각 j(1 <= j <= [n/2])에 대해

자신이 j개의 사탕을 먹을 때의 사탕들의 당도의 합의 최댓값을 구하고자 한다.

당이 떨어져 머리를 굴릴 수 없는 준혁이를 대신해, 여러분이 위의 값을 구해주자.

사탕 timer 1s memory 128MB

사탕 1s 128MB