The 4th(2009) ACM Programming Contest of HUST  Onsite Contest
From: 20091206 12:00:00
To: 20091206 17:00:00
Now: 20170920 01:08:57
Status: Public
I  Signal Beacon
Time Limit: 1s
Memory Limit: 128MB
Submissions: 54 Solved: 21
 Description
 In a remote mountainous area, there are N mountains aligned in straight line. From left to right the ith mountain has height Hi. On each mountain live many plain residents. Now we want to place signal beacons on the peaks of these N mountains, in order for this area to be covered by cell phone signal. It costs Ci Yuan to place a beacon on the peak of the ith mountain. If a beacon is placed on the ith mountain, then the nearest mountain to the left and right of it which is not lower than it will block the signal sent to or from it. For example:
(H) = {1 4 5 6 7 2}, i.e. the first mountain has height 1, the second mountain has height 4 ……
If you place a beacon on the 1st mountain, then the signal can cover first two mountains: 1,2.
If you place a beacon on the 5th mountain, then the signal can cover all mountains.
If you place a beacon on the 3rd mountain, then the signal can cover first 4 mountains: 1, 2, 3, 4.
To make all the mountains covered by signal, what is the minimum total cost by placing signal beacons on some mountains?
 Input
 There are multiple cases.
The first line has a positive number: N (1<=N<=10000).
The second line contains N positive numbers, the ith number is Hi
(1<= Hi <=10^9), height of ith mountain. It is guaranteed that no two mountains have the same height.
The third line contains N positive numbers, the ith number is Ci (1<= Ci <=10^9)，cost of placing a beacon on ith mountain.
 Output
 Out put one line, the minimum total cost to cover all mountains with signal.
 Sample Input

3
1 2 3
1 2 3
 Sample Output

Case #1: 2
 Hint
 Source
 Liu Fei, HUST Campus 2009