농부 존은 최근 N개의 착유기가 있는 새로운 헛간을 구입했습니다 (1 <= N <= 40,000).

착유기의 번호는 왼쪽부터 오른쪽까지 순서대로 1 이상 N 이하의 정수 번호가 적혀있고, 착유기 i는 하루에 M(i) 단위의 우유를 추출할 수 있습니다 (1 <= M(i) <= 100,000).

농부 존은 매일 N개의 착유기 중 일부를 작동시켜 우유를 추출합니다. 안타깝게도 기계들이 너무 가까이 설치되어 있어서 기계 i를 작동시키고 있으면 인접한 두 기계는 그날 사용할 수 없습니다(양쪽 끝 기계에는 인접한 기계가 하나뿐입니다). 농부 존은 매일 작동할 기계의 목록을 조건에 맞게 자유롭게 선택할 수 있습니다.

농부 존은 일련의 D일 동안 추출할 수 있는 최대 우유량을 계산하는 데 관심이 있습니다 (1 <= D <= 50,000). 매일 아침, 농부 존은 착유기 i를 정비하면서 일일 우유 생산량 M(i)가 바뀝니다. 우유 생산은 착유기를 정비한 이후 시작합니다. 농부 존의 정비 계획을 바탕으로, 농부 존이 D일 동안 얼마나 많은 우유를 생산할 수 있는지 알려주십시오(정답은 32비트 정수 범위를 넘을 수 있습니다).

#3855 upload 2 done 2 how_to_reg 2

우유 생산(Optimal Milking) timer 1s memory 128MB

#3855

우유 생산(Optimal Milking) 1s 128MB