G. As I end the Refrain
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cyrano, upon facing Roxane, is elated to have delivered a poetic declaration despite his internal doubts. Soon, another challenge rises in the shape of her now angered suitors. As Cyrano's only weakness is a superficial one, for every parry he swiftly makes a ballade. When he ends the refrain, his sword will have swiftly ended their courage's bane.

Cyrano currently distributes the pastries from Ragueneau's bakery to families around town. There are $$$N$$$ bakeries labeled $$$1$$$ through $$$N$$$, and $$$M$$$ community bakery mailboxes numbered $$$1$$$ through $$$M$$$. Cyrano must make $$$N$$$ total trips, one trip for each bakery, and for each trip he can choose to arrive at a mailbox of his choice. We denote the position of the $$$ith$$$ bakery by $$$x_i$$$ $$$(1\leq i\leq N)$$$, and the position of the $$$jth$$$ mailbox by $$$y_j$$$ $$$(1\leq j\leq M)$$$.

Initially, Cyrano starts from a bakery $$$x_i$$$. From there, traveling from point $$$x_i$$$ to $$$y_j$$$ requires fighting off $$$x_i\cdot y_j$$$ suitors. Upon arriving at destination mailbox $$$y_i$$$, Cyrano is greeted with a horde of $$$k_i$$$ angry suitors (mailboxes can be repeated, in which case $$$k_j$$$ suitors must be fought again). Since he does not want to overwork his sword, Cyrano would prefer to take on the minimum number of total suitors.

Please compute the minimum number of suitors Cyrano has to defeat, modulo $$$10^9+7$$$, to complete his deliveries.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ $$$(1\leq N,M\leq 10^5)$$$, the number of bakeries and number of mailboxes.

The next $$$N$$$ lines contain an integer $$$x_i$$$ $$$(0\leq x_i\leq 10^9)$$$, the location of each bakery.

The next $$$M$$$ lines contain two integers $$$y_j$$$ and $$$k_j$$$ $$$(0\leq y_j, k_j\leq 10^9)$$$, the location of each mailbox and number of suitors gathered at each.

Output

Please print one integer, the amount of suitors Cyrano will have to fight off modulo $$$10^9+7$$$.

Examples
Input
4 4
1
4
5
8
4 1
2 7
3 2
0 20
Output
56
Input
8 8
1
4
10
25
30
50
55
80
5074220 4336121
6504740 353290
5149711 7516664
2920615 99182820
4300097 26060135
7321301 8073770
6718972 8140619
2800643 107037826
Output
204794907
Note

Let us look at the first test case.

Cyrano can initially choose to travel from the first bakery to either the first or third mailbox to fight off $$$5$$$ suitors.

From the second bakery, he will choose to travel to the third mailbox to fight off $$$2+3\cdot 4 = 14$$$ suitors.

From the third bakery, he can either travel to the second or third mailbox to fight off $$$17$$$ suitors.

From the fourth bakery, he will choose to travel to the fourth mailbox to fight off $$$20+ 0\cdot 8=20$$$ suitors.

The total number of suitors he will have to fight is $$$5+14+17+20=56$$$.