2xN 예쁜 타일링
시간 제한2초메모리 제한512 MB
2xN 격자를 최대 A개의 2x1 타일과 최대 B개의 2x2 타일로 채우되, 타일은 90도 회전할 수 있고 미려함의 합이 최대가 되도록 배치한다.
문제
2021년, 정보대 화장실에서 물이 자꾸 넘쳐서 바닥 타일링을 다시 해야 할 지경에 이르렀다. 타일링의 장인 민규는 "언제나 타일링은 예쁘게"라는 좌우명으로 살아왔다. 새로 타일링을 해야 하는 화장실 바닥은 2×N 크기의 격자로 표현된다. 민규에게는 2×1 크기의 타일 A개와 2×2 크기의 타일 B개가 있다. 각 타일에는 "예쁨"의 정도가 있는데, 화장실 바닥의 예쁨은 바닥을 구성하는 타일들의 예쁨의 합이다. 민규는 가지고 있는 타일들로 화장실 바닥의 예쁨이 최대로 되게 타일링하려고 한다. 이때 얻을 수 있는 예쁨의 최댓값은 얼마일까?
예제 1의 예쁨의 최댓값으로 가능한 경우이다. 타일은 90도 회전할 수 있다.
입력
첫째 줄에 정수 N, A, B(1 ≤ N, A, B ≤ 2000, 2 × B + A ≥ N)가 공백으로 구분되어 주어진다.
둘째 줄에 각 2×1 크기 타일의 예쁨을 의미하는 정수 A개가 공백으로 구분되어 주어진다.
셋째 줄에 각 2×2 크기 타일의 예쁨을 의미하는 정수 B개가 공백으로 구분되어 주어진다.
각 타일의 예쁨은 1,000,000 이하의 양의 정수이다.
출력
민규가 가지고 있는 타일들로 얻을 수 있는 화장실 바닥의 예쁨의 최댓값을 출력하시오.