分数: 400 分
问题陈述
高桥有 N 书在他的书架上从左到右排成一排。的 i左起第本书有 A_i 页,并且要将这本书从书架上移走并送到二手书店,高桥必须支付手续费 C_i。留在书架上的图书不收取任何费用。
为了改善书架的外观,高桥想要移除一些书籍,以便剩余书籍的页数为 严格单调递增 从左到右。也就是说,从左到右看剩余的书时,对于任意两本相邻的书,左边的书的页数必须严格小于右边的书的页数。请注意,由于书籍仅被删除而没有重新排列,因此剩余书籍的相对顺序与原始顺序相同。
删除的书籍数量可以是以下任意数字 0 to N,包括在内。当满足严格单调递增条件时 0 or 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
- 第一行包含一个整数 N 代表图书数量。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每本书的页数。在这里, A_i 是页数 i左起第本书。
- 第三行包含 N 整数 C_1, C_2, \ldots, C_N 以空格分隔,代表每本书移除的手续费。在这里, C_i 是高桥必须支付的移除费用 i左起第本书。
输出
在选择要移除的书籍时,一行打印移除的书籍的最低总手续费,以便剩余书籍的页数严格单调递增。
示例输入 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