문제 1044 세종이의 책 읽기(L)
독서를 사랑하는 세종이가 책더미 2개를 발견하고 k권의 책을 읽으려고 한다.
책더미 중간에 있는 책을 빼서 먼저 읽으면 책더미가 쓰러지기 때문에 세종이는 책더미가 무너지지 않도록 각 책더미의 가장 위에 있는 책부터 읽을 수 있다.
세종이가 읽은 책은 책더미에서 제거한다.
세종이가 4권의 책을 C → G → F → E 순서 또는 C → B → A → G 순서로는 읽을 수 있다. 하지만 C → F → B → E 순으로는 읽을 수 없다. 왜냐하면 F위에 G를 읽지 않았기 때문이다.
세종이가 독서에서 느끼는 행복감은 책의 내용과는 관계없이 읽은 책의 페이지 수에 비례한다(신기하게도 이 나라에는 페이지의 수가 음수인 경우도 있다).
세종이가 k권의 책을 읽을 때 최대로 느낄 수 있는 행복감을 구하는 프로그램을 작성하시오.
첫째 줄에는 읽을 책의 수 k와 첫번째 더미에 있는 책의 수 n, 두번째 더미에 있는 책의 수 m이 공백을 기준으로 주어진다.
둘째 줄에는 첫번째 더미에 있는 각 책의 페이지 수(a_i)가 공백을 기준으로 주어진다.
셋째 줄에는 두번째 더미에 있는 각 책의 패이지 수(b_i)가 공백을 기준으로 주어진다.
각 더미에서 책이 입력되는 순서는 위쪽 책으로부터 아래쪽 책의 순으로 입력된다.
(1 <= n, m <= 100,000), (-10,000 <= a_i, b_i <= 10,000), (0 <= k <= n+m)
세종이가 느낄 수 있는 최대 행복감을 출력한다.
5 6 7
1 2 3 4 5 6
4 5 6 0 1 1 7
18