A chain of n relay beacons stands along a coastline, numbered 1 to n from west to east and never reordered. Beacon i has a height h_i, and if it is activated as part of a relay chain it contributes a range bonus r_i to the chain's total reach.
A field engineer wants to activate exactly three beacons, at original positions i < j < k, such that their heights strictly increase: h_i < h_j < h_k. Among every such valid triple, find the maximum possible total range bonus r_i + r_j + r_k. If no valid triple of beacons exists, the chain cannot be built.
Line 1: a single integer n, the number of beacons.
Line 2: n space-separated integers h_1 ... h_n, the beacon heights.
Line 3: n space-separated integers r_1 ... r_n, the range bonuses.
Print a single integer: the maximum total range bonus obtainable from a triple of beacons at positions i < j < k with h_i < h_j < h_k, or -1 if no such triple exists.
3 <= n <= 20001 <= h_i <= 20001 <= r_i <= 10^6Example 1
Input
5 1 3 5 7 9 2 9 4 7 3
Expected
20
Explanation
Heights [1,3,5,7,9] are already strictly increasing at every position, so any triple of positions i<j<k automatically satisfies the height condition. The task reduces to choosing 3 positions maximizing the sum of bonuses. The three largest bonuses are 9 (position 2), 7 (position 4), and 4 (position 3), and positions {2,3,4} already satisfy i<j<k, giving 9+4+7=20, which is the maximum.
Example 2
Input
4 5 4 3 2 10 20 30 40
Expected
-1
Explanation
Heights [5,4,3,2] are strictly decreasing, so no position j has an earlier position with a smaller height and a later position with a larger height simultaneously — in fact no pair of positions i<j even has h_i<h_j. No valid triple exists, so the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →