문제
“언리미티드”의 멤버 성열이는 다른 멤버 성규보다 노래를 더 잘 부르지만 실제로는 성규가 성열이보다 훨씬 파트를 좋게 갖는다. 이에 불만을 가진 성열이는 성규와 일종의 거래(?)를 해서 파트를 바꾸려고 한다. 각 파트에는 시간과 난이도가 자연수로 정해져 있다.
성규는 총 N개의 파트를 맡고 있고, 성열이는 총 M개의 파트를 맡고 있는데, 성열이가 자신이 줄 파트와 가져갈 파트를 선택한 후 맞바꿀 수 있다.
그런데 성규는 자신이 노래를 부르는 시간이 변하지 않기를 바란다. 그래서 성열이가 줄 파트의 시간의 합과 가져갈 파트의 시간의 합이 같게 맞바꿔야 한다.
성열이는 사람들에게 자신의 뛰어난 가창력을 보여주려 하기 때문에, 성규와 파트를 바꾼 후 자신의 파트들의 난이도의 합을 최대화하려고 한다. 성열이가 최적의 방법으로 성규와 파트를 바꾼 후, 성열이가 갖게 되는 파트들의 난이도의 합을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 성규의 파트 수 K와 성열이의 파트 수 Y가 주어진다. (1 ≤ K, Y ≤ 100) 두 번째 줄부터 K개의 줄에는 성규가 갖고 있는 각 파트의 길이 LKi 와 난이도 DKi 가 주어진다. K+2번째 줄부터 Y개의 줄에는 성열이가 갖고 있는 각 파트의 길이 LYi 와 난이도 DYi 가 주어진다. 1 ≤ LKi, DKi, LYi, DYi ≤ 100
<서브태스크> 서브태스크 1 : 1 ≤ K, Y ≤ 5 서브태스크 2 : 1 ≤ K, Y ≤ 15 서브태스크 3 : 성규와 성열이의 모든 파트의 길이는 1이다. 서브태스크 4 : 추가적인 제약조건은 없다.
출력
성열이가 최적의 방법으로 성규와 파트를 바꾼 후, 성열이가 갖게 되는 파트들의 난이도의 합을 출력한다.
예제
4 3
3 1
1 2
2 3
2 2
5 1
3 2
2 4
13
로그인해야 코드를 작성할 수 있어요.