리얼리티 쇼

인기 리얼리티 쇼가 세 번째 시즌 출연자를 모집하고 있다. 1번부터 $n$번까지 번호가 매겨진 지원자 $n$명을 면접했다. 지원자 $i$의 공격성 수준은 $l_i$이고, 이 지원자를 모집하는 데 방송국은 $s_i$루블이 든다.

사회자는 지원자를 $i=1$부터 $i=n$까지 번호 순서대로 검토하고, 각 지원자를 뽑을지 결정한다. 지원자 $i$의 공격성 수준이 이미 뽑힌 지원자 중 누구보다도 엄격하게 높으면, 지원자 $i$는 무조건 탈락한다. 그 밖의 경우에는 사회자가 자유롭게 뽑거나 뽑지 않을 수 있다. 사회자는 총 이익이 최대가 되도록 출연진을 고르려 한다.

방송국의 수익은 다음과 같이 생긴다. 각 공격성 수준 $v$마다 수익성 값 $c_v$가 주어지며, 이 값은 양수일 수도 음수일 수도 있다. 뽑힌 출연자는 모두 번호 순서대로 한 명씩 무대에 등장한다. 출연자 $i$가 무대에 들어올 때 다음이 일어난다.

• 방송국은 $c_{l_i}$루블을 번다. 여기서 $l_i$는 출연자 $i$의 초기 공격성 수준이다.
• 무대 위에 공격성 수준이 같은 출연자가 두 명 있으면 즉시 싸움이 벌어진다. 패자는 병원에 실려 쇼를 떠난다. 승자의 공격성 수준은 1 올라가고, 방송국은 새 수준 $t$에 대해 $c_t$루블을 번다.
• 무대 위 모든 출연자의 공격성 수준이 서로 달라질 때까지 싸움은 계속된다.

사회자는 총 이익이 최대가 되도록 출연진을 고르려 한다. 이익은 무대에서 발생한 총 수익에서 뽑힌 모든 출연자의 비용(뽑힌 $s_i$의 합)을 뺀 값이다. 사회자가 방송을 최대한 수익성 있게 만들도록 도와라.

첫 줄에는 두 정수 $n$과 $m$($1 \le n, m \le 2000$)이 주어진다. $n$은 지원자 수이고, $m$은 초기 공격성 수준의 상한이다.

둘째 줄에는 $n$개의 정수 $l_i$($1 \le l_i \le m$)가 주어진다. 모든 지원자의 초기 공격성 수준이다.

셋째 줄에는 $n$개의 정수 $s_i$($0 \le s_i \le 5000$)가 주어진다. 각 지원자를 뽑는 데 드는 비용(루블)이다.

넷째 줄에는 $n + m$개의 정수 $c_i$($|c_i| \le 5000$)가 주어진다. 각 공격성 수준의 수익성이다.

주어진 조건에서 어떤 출연자의 공격성 수준도 $n + m$을 넘지 않는다는 것이 보장된다.

최대 이익을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 지원자 $1$, $2$, $3$, $5$를 뽑는 것이 최적이다. 이때 모집 비용은 $1 + 2 + 1 + 1 = 5$루블이다. 무대에서 일어나는 일은 다음과 같다.

• 공격성 수준 $4$인 출연자가 들어오고, 방송국은 $4$루블을 번다.
• 공격성 수준 $3$인 출연자가 들어오고, 방송국은 $3$루블을 번다.
• 공격성 수준 $1$인 출연자가 들어오고, 방송국은 $1$루블을 번다.
• 공격성 수준 $1$인 출연자가 또 들어오고, 방송국은 $1$루블을 번다. 싸움이 벌어져 한 명은 떠나고, 다른 한 명은 수준 $2$로 올라간다. 이로 인해 방송국은 추가로 $2$루블을 번다.

총 수익은 $4 + 3 + 1 + 1 + 2 = 11$루블이고, 이익은 $11 - 5 = 6$루블이다.

두 번째 예제에서는 두 번째 지원자의 공격성 수준이 더 높기 때문에 두 명을 모두 뽑을 수 없다. 지원자 1만 뽑는 것이 낫다.