화물열차의 운행 노선은 일자 형태의 노선으로 N개의 역이 1번 역, .. , N번 역 까지 나열되어 있으며 i번 역과 i+1번 역 사이가 선로로 연결되어 있다. (역과 역 사이의 거리는 1이다.)

초기 상태는 2번 역 부터 N번 역까지 역마다 화물이 하나씩 놓여 있고 i번 역에 있는 화물의 가치는 A_i이다.

화물열차는 1번 역에서 출발하며 양방향으로 움직일 수 있다.

각 역에서 그 역에 있는 화물을 열차에 올리거나, 열차에 있는 화물을 그 역에 내릴 수 있다.

단, 무제한으로 열차에 화물을 올릴 수 없고 W개 이하의 화물만 올릴 수 있다.

또한 연료에 제한이 있어 총 이동 거리가 D이하가 되어야 한다.

최대한 가치가 높은 화물들을 1번 역으로 옮기고 싶다. 1번 역으로 옮길 수 있는 최대 화물 가치를 출력하시오.

화물열차 timer 2s memory 1024MB

화물열차 2s 1024MB