소형 기관차

기차는 맨 앞의 기관차 한 대가 여러 객차를 끌고 운행한다. 기관차가 고장나면 전체 기차를 운행할 수 없으므로, 이에 대비해 일부 역에는 소형 기관차 3대를 배치해 두었다. 소형 기관차는 일반 기관차보다 훨씬 적은 수의 객차만 끌 수 있다.

기관차가 고장났을 때 모든 객차를 소형 기관차 3대가 나누어 끌 수는 없다. 그래서 어떤 객차를 끌고 갈지 다음 규칙에 따라 정한다.

1. 소형 기관차 한 대가 최대로 끌 수 있는 객차 수를 미리 정한다. 각 소형 기관차는 이 수보다 많은 객차를 끌 수 없으며, 세 소형 기관차의 한계는 모두 같다.
2. 세 소형 기관차가 운송하는 승객 수의 합을 최대화한다. 각 객차에 탄 승객 수는 미리 알고 있고, 승객은 다른 객차로 이동할 수 없다.
3. 각 소형 기관차는 번호가 연속된 객차들만 끌 수 있다. 객차 번호는 기관차 바로 뒤 객차부터 1번, 2번, ... 순서로 붙어 있다.

예를 들어 객차가 7칸이고, 소형 기관차 한 대가 최대 2칸을 끌 수 있다고 하자. 1번부터 7번까지 각 객차의 승객 수가 다음과 같을 때, 괄호 안 숫자는 객차 번호이다.

세 소형 기관차가 각각 1-2번, 3-4번, 6-7번 객차를 끌면 승객 240명을 운송할 수 있고, 이보다 많은 승객을 운송할 수는 없다.

객차 수, 각 객차의 승객 수, 소형 기관차 한 대가 최대로 끌 수 있는 객차 수가 주어진다. 소형 기관차 3대로 운송할 수 있는 승객 수의 최댓값을 구하시오.

첫째 줄에 기관차가 끌고 가던 객차의 수가 주어진다. 이 수는 50,000 이하이다.

둘째 줄에는 1번 객차부터 차례대로 각 객차에 탄 승객 수가 주어진다. 한 객차의 승객 수는 100명 이하이며, 숫자 사이는 공백 하나로 구분된다.

셋째 줄에는 소형 기관차 한 대가 최대로 끌 수 있는 객차 수가 주어진다. 이 수는 전체 객차 수의 1/3보다 작다.

소형 기관차 3대로 운송할 수 있는 승객 수의 최댓값을 한 줄에 출력한다.