Migrated from Lutece 1349 柱爷大战滑稽王

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

咸鱼历$772002$年，咸鱼王的军队趁着世界屏障力量达到最低谷时，强行撕裂了空间来到了我们的世界

瞄哈哈村则首当其冲！，形势不容乐观

据传，咸鱼王所在的世界有三大尊者，分别是

咸鱼王

滑稽王

挠头王

三个人的实力深不可测，其中以咸鱼王实力最强，因而三人隐隐以咸鱼王为首

阵前

“瞄哈哈村的鼠辈，可有人敢出来与我一战？！”

“滑稽王又来叫阵了！，欺我瞄哈哈村无人吗？”，卿学姐愤怒的说道，话虽如此，瞄哈哈村阵前的气氛却静的可怕，每个人看向滑稽王的眼神中都充满了忌惮之色，竟无一人敢应战.

“据传滑稽王的吃惊诀已经修炼到了大成，其幻化出的吃惊光剑攻击力惊人，与其正面对决，怕是....”，天行廖（狗头军师）在一旁分析到.

在一旁原本静坐的柱爷突然睁开双眼，眼中爆发出惊人光芒

“我可一战，定取滑稽王首级”

诸将易得耳。至如柱者，国士无双

为了简化滑稽王和柱爷的对决，我们将柱爷和滑稽王数据化得到

柱爷的咸鱼神功有$N$个招式，每个招式可以造成$A_{i}$点伤害

滑稽王的吃惊诀有$M$个招式，每个招式可以造成$B_{i}$点伤害

柱爷为了给滑稽王一个下马威，决定在一瞬间打出这$N$个招式，这$N$个招式可以造成A数组与B数组的最长公共子序列长度+1的额外伤害

柱爷现在想知道能够造成多少点额外伤害？

Input

第一行两个整数$N,M$，分别表示咸鱼神功，吃惊诀的招式数目

接下来一行，$N$个整数$A_{i}$，分别表示咸鱼神功第$i$个招式的伤害

接下来一行，$M$个整数$B_{i}$，分别表示吃惊诀第$i$个招式的伤害

数据保证:

• $1 \leq N,M \leq 10^6$

• $|A_{i},B_{i}| \leq 10^{9}$

• $A_{i}$互不相同

Output

输出仅一行，表示柱爷能够造成的额外伤害

Samples

4 4
1 2 3 4
1 2 3 4

5

3 3
1 2 3
3 2 1

2

3 3
1 2 3
4 5 6

1

Note

最长公共子序列（LCS）：不一定要连续！

测试数据没有样例

Resources

2016 UESTC Training for Dynamic Programming