B. 礼物

题目描述

有$n$个人，$m$ 件礼物，每个人对应一个编号$a_i$，每件礼物对应价值$c_i$（递增给出），你可以给第$i$个人送编号$j \leq a_i$的礼物，花费为$c_j$，也可以直接送$c_{a_i}$的现金，每个礼物只有一个，求怎么送礼物使得花费最小。

输入格式

第一行输入两个整数$n, m$

第二行输入$n$个整数，表示$a_1, a_2, \cdots, a_n$

第三行输入$m$个整数，表示$c_1, c_2, \cdots, c_m$

输出格式

输出一个整数，表示最小花费

样例输入1

5 4
2 3 4 3 2
3 5 12 20

样例输出1

30

样例输入2

5 5
5 4 3 2 1
10 40 90 160 250

样例输出2

190

数据范围

对于30%的数据，$n \leq 10$

对于另外30%的数据，$n \leq 5000, m = 2$

对于100%的数据，$n, m \leq 2 \times 10^5, c_1 \leq c_2 \cdots \leq c_m \leq 10^9, 1 \leq a_i \leq m$