题目背景

Pharloom 是一个神秘的王国，丝线与歌是那里最强大的力量。多弦琴是 Pharloom 的一种强大武器，正如多项式是 OI 中的强大武器。

因为你很讨厌多项式，你决定摧毁多弦琴。

题目描述

下面这部分题面只是为了帮助你理解题意，并没有详细的解释。更为严谨清晰的叙述见形式化题意。

多弦琴由两根支柱和连接两根支柱的 $m$ 条弦组成。每根支柱上都均匀安放着 $n$ 个固定点，第 $i$ 条弦连接上方支柱的第 $u_i$ 个固定点和下方支柱的第 $v_i$ 个固定点。

上图是一把多弦琴

为了摧毁多弦琴，你可以进行若干次切割操作。在一次切割操作中，你可以选择上方支柱的某一个固定点 $u$ 和下方支柱的一个固定点 $v$，所有被 $u$ 到 $v$ 的连线从左到右穿过的弦都将被破坏。但同时，你需要付出 $a_u \times b_v$ 的代价。

形式化题意：有 $m$ 条弦，一条弦可以抽象为一个二元组 $(u,v)$，你可以进行任意次切割操作，一次切割操作你将选择两个下标 $i$ 和 $j$ 满足 $i,j \in [1,n]$，然后所有满足 $u>i,v<j$ 的弦 $(u,v)$ 都将被破坏，同时你将付出 $a_i \times b_j​$ 的代价。求破坏所有弦的最小代价和。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$。

接下来 $m$ 行每行两个整数 $u,v$，表示有一条弦 $(u,v)$。

以上输入的意义见题目描述。

输出格式

一行一个整数，答案。

5 2
3 9 1 9 9
9 9 1 9 3
2 1
5 4

6

5 1
9 9 9 9 1
1 9 9 9 9
3 3

81

提示

样例解释

对于第一组样例，使用两次切割，分别为 $(1,3)$，$(3,5)$，花费代价 $3 \times 1 + 1 \times 3 = 6$。

对于第二组样例，注意切割 $(5,1)$ 不能使弦 $(3,3)$ 消失。

---

数据范围

「本题采用捆绑测试」

对于所有测试点，保证 $1 \leq n, m \leq 3\times 10^5$，$2 \leq u \leq n$，$1 \leq v \leq n-1$，$1 \leq a_i,b_i \leq 10^6$。

$\text{Subtask 1 (21 pts)}$ $n,m \leq 6$。

$\text{Subtask 2 (3 pts)}$ $m=1$。

$\text{Subtask 3 (1 pts)}$ $a_1=b_n = 1$。

$\text{Subtask 4 (25 pts)}$ $n,m \leq 100$。

$\text{Subtask 5 (29 pts)}$ $n,m \leq 10^3$。

$\text{Subtask 6 (21 pts)}$ 无特殊限制。

---

提示

如果你认真观察了数据范围，你会发现这把多弦琴一定能够被破坏。