31880번 - K512컵 개최!

문제

2024년도부터 Sogang ICPC Team에서는 학회원들의 대회 경험을 쌓고 학회원들끼리의 친목 증진을 위해 매년 K512컵을 개최한다!

대회에서 중요한 요소 중 하나는 행운이다. 참가자들의 초기 행운 수치는 모두 0ドル$이며, 근수는 참가자들의 행운 수치를 변화시킬 수 있는 두 종류의 주문서를 참가자들에게 각각 $N,ドル $M$장씩 나눠준다. 참가자들은 주어진 주문서를 적절한 순서로 전부 소모하여 자신의 행운 수치를 변화시켜야 한다.

1. $N$장의 주문서에는 각각 수 $a_i$ (1ドル \le i \le N$)가 적혀 있으며, 각각의 주문서를 소모할 때 행운 수치는 현재 행운 수치에서 $a_i$만큼 더해진 값이 된다.
2. $M$장의 주문서에는 각각 수 $b_i$ (1ドル \le i \le M$)가 적혀 있으며, 각각의 주문서를 소모할 때 행운 수치는 현재 행운 수치에서 $b_i$만큼 곱해진 값이 된다.

즉 현재 행운 수치를 $P$라고 할 때, 행운 수치는 각각 $P + a_i,ドル $P \times b_i$로 변화한다.

참가자들은 자신의 행운 수치를 최대화하여 모두 K512컵에서 좋은 결과가 있기를 바라고 있다. 당신도 입력으로 주어진 주문서를 적절한 순서로 모두 소모하여 행운 수치를 최대화해 보자!

입력

첫 번째 줄에 각 종류의 주문서들의 개수인 $N$과 $M$이 공백으로 구분되어 주어진다. (1ドル \le N, M \le 12$)

두 번째 줄에는 $N$개의 정수 $a_1, ..., a_N$이 공백으로 구분되어 주어진다. (0ドル \le a_i \le 10$)

세 번째 줄에는 $M$개의 정수 $b_1, ..., b_M$이 공백으로 구분되어 주어진다. (0ドル \le b_i \le 10$)

출력

주어진 주문서로 만들 수 있는 행운 수치의 최댓값을 출력한다.

제한

노트

큰 수를 다룰 때는 정수 오버플로우 현상에 주의해야 하며, 언어별로 다음과 같은 64비트 정수 자료형을 사용하는 것이 권장된다.

• C, C++: long long (scanf/printf의 형식지정자로는 %lld 사용)
• Java, Kotlin: long