Problem Statement

In this world, there are $K$ types of gems numbered from $1$ to $K(=4)$. The value per unit size of a gem of type $i$ is $W_i$.

Snuke has $N$ gems. The $i$-th gem is of type $A_i$ and has size $B_i$. Also, Snuke has $N$ boxes, where the $i$-th box has size $i$.

Snuke will now put one gem in each box. When a gem's size is larger than the box, the gem is cut to fit in the box. That is, when gem $i$ is put in box $j$, its value becomes $W_{A_i} \times \min(B_i, j)$.

Find the maximum possible sum of gem values.

Constraints

• $K = 4$
• $1 \leq W_1 < W_2 < \cdots < W_K \leq 10^6$
• $1 \leq N \leq 250000$
• $1 \leq A_i \leq K$
• $1 \leq B_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
W_1 W_2 \ldots W_K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer.