35056번 - 트윈 타워 (Easy)

문제

이 문제는 Hard 버전과 $N$의 제한을 제외하면 동일합니다.

경곽시티에는 일렬로 이어진 $N$개의 개발 부지가 있다.

경곽시티에는 현재 아무 타워와 통로도 없는 상태로 당신은 이 중 일부 부지를 선택해 타워를 건설하고 통로를 만들어 도시 가치를 최대화하려 한다. 다음은 타워 및 통로에 관해 여러분들이 알아야 할 정보다.

1. $i$번 부지에 타워를 지으면, 도시는 $A_i$만큼의 가치를 얻게 된다. 이 경우 1ドル$의 비용이 든다. (1ドル \leq i \leq N$)
2. $i$번 부지와 $i+1$번 부지에 둘 다 타워가 건설되어 있다면, 당신은 $i$번 타워와 $i+1$번 타워를 잇는 통로를 만들어 트윈 타워로 만들 수 있다. 이 경우 $B_i$만큼의 가치를 얻게 된다. 통로를 만드는 과정은 아무 비용이 들지 않는다. (1ドル \leq i \leq N-1$)
3. 하나의 타워에는 최대 하나의 통로가 연결될 수 있다. 즉, $i$번 타워와 $i+1$번 타워를 잇는 통로, $i+1$번 타워와 $i+2$번 타워를 잇는 통로는 동시에 만들 수 없다. (1ドル \leq i \leq N-2$)

가능한 1ドル$부터 $N$까지의 비용에 대해, 타워와 통로를 적당히 건설해 얻을 수 있는 최대 가치를 구해보자.

입력

첫 번째 줄에 $N$이 주어진다.(2ドル \leq N \leq 2\ 000$)

두 번째 줄에 $N$개의 정수 $A_1, ,円 A_2, ,円 \cdots, ,円 A_N$이 공백으로 구분되어 주어진다. (0ドル \leq A_i \leq 10^9$)

세 번째 줄에 $N-1$개의 정수 $B_1, ,円 B_2, ,円 \cdots, ,円 B_{N - 1}$이 공백으로 구분되어 주어진다. (0ドル \leq B_i \leq 10^9$)

출력

첫 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 비용 $i$로 얻을 수 있는 최대 가치를 출력하라.

제한

노트