Problem Background

Pharloom is a mysterious kingdom where the power of Strings and Songs is the most potent. The multi-stringed instrument is a powerful weapon in Pharloom, just as polynomials are a powerful tool in OI.

Because you dislike polynomials, you decide to destroy the multi-stringed instrument.

Problem Description

The following part of the problem statement is intended to help you understand the problem, but it does not provide detailed explanations. For a more rigorous and clear description, see the formal problem statement.

The multi-stringed instrument consists of two pillars connected by $m$ strings. Each pillar has $n$ evenly spaced fixed points, with the $i$-th string connecting the $u_i$-th fixed point on the upper pillar to the $v_i$-th fixed point on the lower pillar.

The above image is a multi-stringed instrument.

To destroy the instrument, you can perform several cutting operations. In a cutting operation, you can choose a fixed point $u$ on the upper pillar and a fixed point $v$ on the lower pillar. All strings that are crossed from left to right by the line connecting $u$ and $v$ will be destroyed. However, you will incur a cost of $a_u \times b_v$.

Formal Problem Statement: There are $m$ strings, each string can be abstracted as a tuple $(u, v)$. You can perform any number of cutting operations. In each operation, you will choose two indices $i$ and $j$ such that $i, j \in [1, n]$, and all strings $(u, v)$ that satisfy $u > i, v < j$ will be destroyed, with a cost of $a_i \times b_j$. Find the minimum total cost to destroy all strings.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$.

The next $m$ lines each contain two integers $u, v$, representing a string $(u, v)$.

Refer to the problem description for the meaning of the input.

Output Format

A single integer, the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6

Sample Input #2

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

Sample Output #2

81

Notes/Hints

Sample Explanation

For the first sample, use two cuts, $(1, 3)$ and $(3, 5)$, with a cost of $3 \times 1 + 1 \times 3 = 6$.

For the second sample, note that cutting $(5, 1)$ does not make the string $(3, 3)$ disappear.

Data Range

"This problem uses batched testing."

For all test cases, it is guaranteed that $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)}$ No special restrictions.

Hints

If you carefully observe the data range, you will find that this multi-stringed instrument can definitely be destroyed.

见题面 Input 部分

见题面 Output 部分