Description

给定一个n个点m条边的有向弱连通图，每个点均匀点权di和修改耗时wi，每次修改可以花费wi的时间把di 加1或者减1，求最少消耗多少时间，使得∀(u,v)∈E,du≤dv。

Format

Input

输入共包括m+3行

第一行包含两个整数n,m表示点数和边数。

第二行包含n个整数，第i个整数表示第i个点的点权di。

第三行包含n个整数，第i个整数表示第i个点的修改耗时wi。

第4m+3行，每行包含两个整数ui,vi表示有向图种的一条由ui到vi的有向边。

n<=300000,m=n或m=n-1

Output

输出包含一个整数，表示最小总耗时。

Samples

3 3
5 9 8
1 2 3
1 2
2 3
3 1

5

样例解释 1

限制为 d1<=d2, d2<=d3,d3<=d1，即要求d1=d2=d3，故将 d1加3至8，d2减1至8最优 最优耗时为1*|5-8|+2*|9-8|+3*|8-8|=5