에리 카드

공유 카드 N장과 팀 카드 N장이 주어지고 상대가 팀 카드 K장을 막아 우리 점수를 최소로 만들려 할 때, 우리가 얻을 수 있는 최대 점수를 구한다.

보통6정렬그리디완전 탐색수학아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

2468년 해왕성 올림픽에서 에리 카드가 정식 종목으로 채택되었다. 각 팀은 공유 숫자카드 NN장과 팀 숫자카드 NN장을 받고 경기를 시작한다.

경기는 이렇게 진행된다. 먼저 상대 팀이 우리 팀의 팀 숫자카드 중 KK장을 견제한다. 견제된 카드는 낼 수 없다. 견제가 모두 끝나면 우리 팀은 공유 숫자카드에서 한 장, 견제되지 않은 팀 숫자카드에서 한 장을 골라 낸다. 두 카드에 적힌 수의 곱이 우리 팀의 점수다. 이어서 상대 팀도 같은 방식으로 점수를 얻고, 점수가 더 높은 팀이 이긴다.

상대 팀은 항상 최선의 방법으로 견제한다. 즉 우리 팀이 얻을 수 있는 점수를 가장 작게 만드는 KK장을 고른다. 이때 우리 팀이 얻을 수 있는 최대 점수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 NNKK가 주어진다. (0K<N1000 \le K < N \le 100)

둘째 줄에 공유 숫자카드 NN장에 적힌 정수가 주어진다.

셋째 줄에 팀 숫자카드 NN장에 적힌 정수가 주어진다.

카드에 적힌 수는 10000-10000 이상 1000010000 미만의 정수다.

출력

우리 팀이 얻을 수 있는 최대 점수를 한 줄에 출력한다.

힌트

예제에서 상대 팀은 팀 숫자카드 2장을 견제할 수 있다. 가장 큰 점수를 만들 수 있는 카드 44와 카드 33을 견제하므로, 남은 팀 숫자카드는 1-1, 00, 22다. 우리 팀은 공유 숫자카드의 55와 팀 숫자카드의 22를 내서 1010점을 얻는다.