에리 카드
시간 제한1초메모리 제한128 MB
공유 카드 N장과 팀 카드 N장이 주어지고 상대가 팀 카드 K장을 막아 우리 점수를 최소로 만들려 할 때, 우리가 얻을 수 있는 최대 점수를 구한다.
문제
2468년 해왕성 올림픽에서 에리 카드가 정식 종목으로 채택되었다. 각 팀은 공유 숫자카드 장과 팀 숫자카드 장을 받고 경기를 시작한다.
경기는 이렇게 진행된다. 먼저 상대 팀이 우리 팀의 팀 숫자카드 중 장을 견제한다. 견제된 카드는 낼 수 없다. 견제가 모두 끝나면 우리 팀은 공유 숫자카드에서 한 장, 견제되지 않은 팀 숫자카드에서 한 장을 골라 낸다. 두 카드에 적힌 수의 곱이 우리 팀의 점수다. 이어서 상대 팀도 같은 방식으로 점수를 얻고, 점수가 더 높은 팀이 이긴다.
상대 팀은 항상 최선의 방법으로 견제한다. 즉 우리 팀이 얻을 수 있는 점수를 가장 작게 만드는 장을 고른다. 이때 우리 팀이 얻을 수 있는 최대 점수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 과 가 주어진다. ()
둘째 줄에 공유 숫자카드 장에 적힌 정수가 주어진다.
셋째 줄에 팀 숫자카드 장에 적힌 정수가 주어진다.
카드에 적힌 수는 이상 미만의 정수다.
출력
우리 팀이 얻을 수 있는 최대 점수를 한 줄에 출력한다.
힌트
예제에서 상대 팀은 팀 숫자카드 2장을 견제할 수 있다. 가장 큰 점수를 만들 수 있는 카드 와 카드 을 견제하므로, 남은 팀 숫자카드는 , , 다. 우리 팀은 공유 숫자카드의 와 팀 숫자카드의 를 내서 점을 얻는다.