장갑
시간 제한2초메모리 제한128 MB
색상별 왼쪽, 오른쪽 장갑 개수가 주어질 때, x개의 왼쪽 장갑과 y개의 오른쪽 장갑을 어떻게 뽑아도 항상 같은 색 쌍이 존재하게 되는 x+y의 최솟값(동률이면 x가 최소인 것)을 구합니다.
문제
색이 N가지인 장갑이 있다. 왼손 장갑은 왼쪽 통에, 오른손 장갑은 오른쪽 통에 들어 있으며, 각 색의 개수는 알고 있다. 지하실이 어두워서 통에서 꺼낸 장갑의 색은 고를 수 없다.
왼쪽 통에서 x개, 오른쪽 통에서 y개를 가져왔을 때, 가능한 어떤 선택에서도 같은 색의 왼손 장갑과 오른손 장갑이 적어도 한 쌍 포함되면 (x, y)가 보장된다고 하자.
보장되는 쌍 중 x + y가 최소인 쌍을 구한다. 여러 쌍이 같은 최소 합을 가지면 x가 가장 작은 쌍을 출력한다.
입력
첫 줄에 색의 수 N (1 <= N <= 20)이 주어진다.
둘째 줄에는 왼쪽 통에 들어 있는 색별 왼손 장갑의 수 L_1, L_2, ..., L_N이 주어진다.
셋째 줄에는 오른쪽 통에 들어 있는 색별 오른손 장갑의 수 R_1, R_2, ..., R_N이 주어진다.
모든 장갑 수는 0 이상 10^8 이하의 정수이며, 보장되는 쌍이 존재하는 입력만 주어진다.
출력
선택해야 하는 왼손 장갑의 수 x와 오른손 장갑의 수 y를 각각 한 줄에 출력한다.
참고
보장 여부는 최악의 경우로 판단한다. 예를 들어 어떤 색 집합의 왼손 장갑만으로 x개를 채울 수 있고, 그 밖의 색의 오른손 장갑만으로 y개를 채울 수 있다면 같은 색 쌍을 피하는 선택이 가능하므로 (x, y)는 보장되지 않는다.