색이 있는 슬라임 공

시간 제한2초메모리 제한2048 MB

요약

줄 위의 슬라임 공을 모두 팔 때 질량을 올리는 비용을 뺀 최대 순이익을 구합니다. 사이에 있는 공이 팔리면 같은 색 이웃이 하나로 합쳐집니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 구간
정답자: 아직 제출이 없습니다

문제

한 줄로 놓인 슬라임 공 $n$ 개가 있다. $i$ 번째 슬라임 공의 색은 $c_i$ , 질량은 $m_i$ 이다. 연산은 원하는 만큼 할 수 있다. 연산 한 번마다 슬라임 공 하나의 질량이 1 증가하고, 연산당 비용 $w$ 가 든다. 슬라임 공의 질량이 $k$ 이상이 되면 불안정해져서 다음 연산 전에 반드시 팔아야 한다. 질량이 $k$ 이상인 슬라임 공만 팔 수 있다. 질량이 $i$ 인 슬라임 공을 팔면 $p_i$ 의 수익을 얻는다. $p_i - p_{i-1} < w$ 가 보장되지만, $p_i$ 가 반드시 단조 증가하지는 않는다.

슬라임 공을 팔면 양옆의 공들이 빈틈을 메우도록 이동한다. 팔린 공의 양옆 이웃이 같은 색이었다면, 두 공은 합쳐져 질량의 합을 가진 하나의 슬라임 공이 된다. 이 새 공도 팔아야 할 수 있으며, 이 과정은 이어진다. 모든 슬라임 공을 판 뒤 얻을 수 있는 순이익의 최댓값을 구하라.

입력

첫 줄에 양의 정수 $n$ , $k$ , $w$ 가 주어진다 ( $1 \le n \le 150$ , $2 \le k \le 10$ , $1 \le w \le 10^6$ ). 둘째 줄에는 양의 정수 $n$ 개가 주어지며, $i$ 번째 값은 슬라임 공의 색 $c_i$ 이다 ( $1 \le c_i \le n$ ). 처음에는 이웃한 공의 색이 같지 않다( $c_i \ne c_{i-1}$ ). 셋째 줄에는 양의 정수 $n$ 개가 주어지며, $i$ 번째 값은 초기 질량 $m_i$ 이다 ( $1 \le m_i < k$ ). 넷째 줄에는 정수 $k - 1$ 개 $p_k, p_{k+1}, \ldots, p_{2k-2}$ 가 주어진다 ( $0 \le p_i \le 10^9$ , $p_i - p_{i-1} < w$ ).

출력

모든 슬라임 공을 판 뒤의 순이익 최댓값을 정수 하나로 출력한다.

힌트

예시에서는 먼저 색이 3인 슬라임 공의 질량을 올린다. 그러면 공이 팔려 5의 수익을 얻는다. 다음으로 색이 1인 공의 질량을 두 번 올린 뒤 팔아 5를 얻는다. 이어서 색이 2인 두 공이 합쳐져 팔리고 7을 얻는다. 연산 세 번의 총비용은 18이므로 순이익은 -1이다. 이보다 나은 풀이는 없다.

예제1

예제 1
입력
```
4 5 6
2 1 2 3
3 3 3 4
5 7 9 11
```
예상 출력
```
-1
```