18230번 - 2xN 예쁜 타일링

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 이하의 양의 정수이다.

민규가 가지고 있는 타일들을 이용해서 얻을 수 있는 화장실 바닥의 예쁨의 최댓값을 출력하시오.