시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 30 8 3 27.273%

문제

당신은 게임을 하다 걸려서 사회봉사를 해야 한다. 당신은 2일동안 길 하나의 쓰레기를 줏으려 한다. “이런 젠장”

어떻게 줍냐면, 무게가 증가되는 순서대로 줍는다. 그런데 문제는, 가방이 고물이라 한번 물건을 넣으면 그 크기에 맞게 가방이 변형되어 버린다. 그러면 당신은 그 가방에는 딱 크기가 맞는 쓰레기만 넣을 수 있다.

요컨데, 첫날 줍는 쓰레기랑 둘 쨋날 줍는 쓰레기가 같아야 한다는 것이다.

당신은 가장 많이 쓰레기를 몹고 싶다. 그런데 옆집 거지친구 오민식이 당신이 첫날 가방에 쓰레기를 담지 않은 가방이 있다면 그 가방을 빼앗아간다.

당신은 특유의 예지력으로 오늘과 내일, 길거리에 쓰레기가 어떤 식으로 놓여있을지 안다.

당신은 하루마다 최대 몇 개의 쓰레기를 주울 수 있는가?

입력

첫 번째 줄에는 쓰레기의 개수 N이 주어진다. (N<=1,000) 두 번째 줄에는 첫쨋날 각각 쓰레기의 양이 위치 순서대로 N개 주어진다. 세 번째 줄에는 둘쨋날 각각 쓰레기의 양이 위치 순서대로 주어진다. 당신은 아침마다 1번 쓰레기가 있는 위치에서 출발하며, 쓰레기를 줍고 나면 뒤로 돌아가서 쓰레기를 줏을 수 없다.

출력

하루 마다 줏을 수 있는 쓰레기의 개수의 최대를 출력한다.

예제 입력

10
1 2 3 4 5 6 7 8 9 10
1 3 5 7 9 2 4 6 8 10

예제 출력

6

힌트

출처