/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は本棚に N 冊の本を左から一列に並べています。左から i 番目の本のページ数は A_i であり、この本を本棚から取り除いて古本屋に引き取ってもらうには、高橋君が手数料 C_i を支払う必要があります。本棚に残す本には手数料はかかりません。
高橋君は本棚の見栄えを良くするため、いくつかの本を取り除き、残った本のページ数が左から右に向かって狭義単調増加になるようにしたいと考えています。すなわち、残った本を左から順に見たとき、どの隣り合う 2 冊についても左の本のページ数が右の本のページ数より真に小さくなるようにします。なお、本を取り除くだけで並べ替えは行わないため、残った本の相対的な並び順は元の並び順と同じです。
取り除く冊数は 0 冊以上 N 冊以下の任意の冊数でよいものとします。残った本が 0 冊または 1 冊の場合も狭義単調増加の条件は満たされるものとします。
残った本のページ数が左から順に見て狭義単調増加となるように取り除く本の集合を選ぶとき、取り除いた本の手数料の合計の最小値を求めてください。
制約
- 1 \leq N \leq 5000
- 1 \leq A_i \leq 10^9
- 1 \leq C_i \leq 10^9
- 入力はすべて整数である。
入力
N A_1 A_2 \ldots A_N C_1 C_2 \ldots C_N
- 1 行目には、本の冊数を表す整数 N が与えられる。
- 2 行目には、各本のページ数を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。ここで A_i は左から i 番目の本のページ数である。
- 3 行目には、各本を取り除く際の手数料を表す N 個の整数 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。ここで C_i は左から i 番目の本を取り除く際に高橋君が支払う手数料である。
出力
残った本のページ数が狭義単調増加となるように取り除く本を選んだとき、取り除いた本の手数料の合計の最小値を 1 行で出力せよ。
入力例 1
5 3 1 4 1 5 10 20 30 40 50
出力例 1
50
入力例 2
4 5 5 5 5 3 1 4 2
出力例 2
6
入力例 3
10 10 3 7 5 8 2 9 1 6 4 5 3 8 2 7 1 6 4 9 10
出力例 3
31
入力例 4
20 15 8 23 42 11 37 5 29 44 18 3 50 33 21 46 9 38 27 41 12 7 12 3 9 15 6 20 4 11 8 18 2 14 10 5 16 1 13 7 19
出力例 4
135
入力例 5
1 1000000000 1000000000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi has N books arranged in a row from left to right on his bookshelf. The i-th book from the left has A_i pages, and to remove this book from the bookshelf and have it taken by a used bookstore, Takahashi must pay a handling fee of C_i. No fee is charged for books that remain on the bookshelf.
To improve the appearance of his bookshelf, Takahashi wants to remove some books so that the page counts of the remaining books are strictly monotonically increasing from left to right. That is, when looking at the remaining books from left to right, for any two adjacent books, the page count of the left book must be strictly less than the page count of the right book. Note that since books are only removed and not rearranged, the relative order of the remaining books is the same as the original order.
The number of books removed may be any number from 0 to N, inclusive. The strictly monotonically increasing condition is considered satisfied when 0 or 1 books remain.
Find the minimum total handling fee of the removed books when choosing which books to remove so that the page counts of the remaining books are strictly monotonically increasing from left to right.
Constraints
- 1 \leq N \leq 5000
- 1 \leq A_i \leq 10^9
- 1 \leq C_i \leq 10^9
- All input values are integers.
Input
N A_1 A_2 \ldots A_N C_1 C_2 \ldots C_N
- The first line contains an integer N representing the number of books.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the page counts of each book. Here, A_i is the page count of the i-th book from the left.
- The third line contains N integers C_1, C_2, \ldots, C_N separated by spaces, representing the handling fees for removing each book. Here, C_i is the handling fee Takahashi must pay to remove the i-th book from the left.
Output
Print in one line the minimum total handling fee of the removed books when choosing which books to remove so that the page counts of the remaining books are strictly monotonically increasing.
Sample Input 1
5 3 1 4 1 5 10 20 30 40 50
Sample Output 1
50
Sample Input 2
4 5 5 5 5 3 1 4 2
Sample Output 2
6
Sample Input 3
10 10 3 7 5 8 2 9 1 6 4 5 3 8 2 7 1 6 4 9 10
Sample Output 3
31
Sample Input 4
20 15 8 23 42 11 37 5 29 44 18 3 50 33 21 46 9 38 27 41 12 7 12 3 9 15 6 20 4 11 8 18 2 14 10 5 16 1 13 7 19
Sample Output 4
135
Sample Input 5
1 1000000000 1000000000
Sample Output 5
0