← 返回题目列表

AtCoder · awc0081_d

D. 整理书架

中文机器翻译题面 查看原题

分数: 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