Y. Grocery shopping
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Auchenai graduated from UIUC last semester and started to work!

Unfortunately, he wants to do some grocery shopping but has only limited time. There are $$$n$$$ shops that Auchenai wants to visit, and shopping at shop $$$i$$$ takes exactly $$$t_i$$$ units of time. What is even worse, there are $$$m$$$ other people — the $$$j$$$-th person will join the queue of shop $$$s_j$$$ at time $$$u_j$$$.

At time $$$0$$$, Auchenai may choose any one shop to visit first. After finishing shopping at one shop, he may immediately go to any other unvisited shop. Moving between shops takes no time.

Each shop has exactly one queue and serves people one by one in arrival order. If Auchenai arrives at a shop while someone is being served or waiting in line, he must wait until all people before him finish. If several people arrive at the same time, all other people are considered to join before Auchenai. Every person shopping at shop $$$i$$$, including Auchenai, occupies the shop for exactly $$$t_i$$$ units of time.

Help Auchenai find the earliest possible time that he can finish shopping (i.e., the moment he finishes shopping at the last shop).

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 18$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$t_1, t_2, \ldots ,t_n$$$ ($$$ 1 \leq t_i \leq 10^9$$$), where $$$t_i$$$ is the time needed to shop at shop $$$i$$$.

Each of the next $$$m$$$ lines contains two integers $$$s_j$$$ and $$$u_j$$$, ($$$1 \leq s_j \leq n$$$, $$$1 \leq u_j \leq 10^9$$$), meaning that the $$$j$$$-th person joins the queue of shop $$$s_j$$$ at time $$$u_j$$$.

Output

Output a single integer — the earliest possible time that Auchenai can finish shopping.

Examples
Input
2 2
2 3
1 1
2 2
Output
5
Input
2 2
2 3
1 3
2 2
Output
7
Input
3 9
3 3 3
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9
Output
11
Input
4 7
5 4 2 5
1 4
1 2
2 2
2 4
4 5
1 3
2 1
Output
19