Migrated from Lutece 2041 游乐园之行

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

在子辉经常和 Sakura 探讨各种问题的过程中，他们的关系迅速升温。这一天，子辉邀请 Sakura 一起去游乐园玩， Sakura 欣然接受。

当然，出来玩也带有浓厚的数学味道。 子辉和 Sakura 各自准备有一个长度为$n$的数列，记为A和C，表示各自对于各个项目的喜爱程度。分别编号都是从$1$到$n$，再给出$m$个数对$(d, e)$，表示A数列的第$d$个项目可以跟C数列的第$e$个项目匹配，当这两个项目被匹配上了，子辉和Sakura 就会获得这两个数之和的开心值，但是每个人的每个项目最多被匹配一次，而且匹配不能相交。也就是说，假设$A(i)$和$C(j)$匹配了，那么不能存在一个匹配$A(u)$和$C(v)$满足($u < i$ and $v > j$) or ($u > i$ and $v < j$)。求问最后最多能获得多少的开心值。

Input

第一行包含两个整数$n$($1 <= n <= 100000$), $m$($1 <= m <= 300000$) 接下来m行，每行两个整数$(d, e)$表示$A(d)$可以跟$C(e)$匹配。 接下来两行，每行n个整数，分别表示A数列和C数列，保证数列中每个数绝对值小于$100$

Output

输出一行一个整数表示最大得分。

Samples

4 4
1 2
2 1
3 4
3 3
4 4 5 1
2 3 5 6

18

Resources

2018 UESTC Training for Dynamic Programming