고도 상승 관측 계획

문제

산꼭대기 천문대에서는 밤새 한 줄로 늘어선 N개의 관측 대상을 번호 순서대로 지나가며 관측 계획을 짠다. i번째 대상은 고도 h_i 에 있고, 관측하면 가치 w_i 를 얻는다. 가치는 음수일 수도 있는데, 이는 장비 소모가 얻는 자료보다 큼을 뜻한다. 망원경은 한 번 위로 돌리면 내려오지 않는 구조라서, 관측할 대상들을 번호가 증가하는 순서로 고르되 고르는 대상의 고도는 엄격하게 증가해야 한다. 즉 고도가 같은 두 대상을 모두 고를 수는 없다. 대상을 하나도 고르지 않는 계획은 허용되지 않으며, 최소한 한 개의 대상은 반드시 관측해야 한다. 고른 대상들의 가치 합이 가장 큰 계획을 찾아 그 합을 출력하는 프로그램을 작성하시오. 모든 가치가 음수라면 가장 큰 가치 하나만 고르는 것이 최선일 수 있다. 모든 수는 정수이며, 답은 항상 존재한다.

입력

첫 줄에 대상의 수 N 이 주어진다. (1 ≤ N ≤ 200,000) 둘째 줄에 고도 h_1, h_2, ..., h_N 이 공백으로 구분되어 주어진다. (1 ≤ h_i ≤ 1,000,000,000) 셋째 줄에 가치 w_1, w_2, ..., w_N 이 공백으로 구분되어 주어진다. (-1,000,000,000 ≤ w_i ≤ 1,000,000,000)

출력

조건을 만족하는 계획에서 얻을 수 있는 가치 합의 최댓값을 한 줄에 출력한다.

5
3 1 4 2 5
2 5 -1 3 4

12

4
5 5 5 5
-3 -1 -7 -2

-1

4
1 2 3 4
4 -5 3 -1

7

출처: Devin.KR 자체 제작