Sličice

Nikola는 축구 선수 사진이 들어 있는 앨범을 모으는 것을 좋아한다. 그는 친구들과 함께 현재 모으고 있는 앨범을 바탕으로 직접 만든 게임을 한다. 그 앨범의 사진들은 N개의 팀으로 나뉘어 있고, 각 팀에는 정확히 M명의 축구 선수가 있다. 게임의 주요 규칙은 i번째 팀에 대해 얻는 총점이 Bx라는 것이다. 여기서 x는 그가 그 팀의 축구 선수 사진 중 서로 다른 사진을 모은 개수이다. 그들은 또한 배열 B가 증가한다는 것, 즉 어떤 팀의 서로 다른 축구 선수 사진을 더 많이 모을수록 점수가 더 많거나 같다는 것에 동의했다.

Nikola는 게임에서 최대한 많은 점수를 얻고 싶어 한다. 각 팀 x에 대해 Nikola가 현재 가지고 있는 그 팀의 서로 다른 사진 개수 Px는 알려져 있다.

Ivan은 Nikola의 친구로, 이미 앨범을 두 번 모두 모았고, Nikola가 친구들과 하는 게임에 대해 듣고 나서 Nikola가 원하는 K장의 사진을 주기로 했다. 이 기쁜 소식을 들은 Nikola는 Ivan이 K장의 사진을 준 후 자신이 가질 수 있는 최대 점수가 얼마인지 궁금해졌다. 너무 흥분한 나머지 계산을 하지 못하는 그는 당신에게 답을 구한다.

첫째 줄에 정수 N, M, K가 주어진다 (1 ≤ N, M ≤ 500, 1 ≤ K ≤ min(N·M, 500)).

둘째 줄에 N개의 음이 아닌 정수로 이루어진 배열 P가 주어진다 (0 ≤ Pi ≤ M).

셋째 줄에 M+1개의 음이 아닌 정수로 이루어진 배열 B가 주어진다 (0 ≤ Bi ≤ 100 000). Bi는 한 팀의 서로 다른 사진 i개(0 ≤ i ≤ M)에 대해 Nikola가 얻는 점수이다.

0과 M-1 사이의 모든 t에 대해 Bt ≤ Bt+1이다.

또한 K ≤ N·M - (P1 + P2 + … + PN)이다.

Nikola의 질문에 대한 답을 한 줄에 출력한다.