Dormitory Parcel Delivery

A dormitory of the Korea Science Academy has an entrance and $2N + 1$ rooms arranged in a straight line. The $i$-th room from the left is room $i$, and the entrance is to the left of room $1$. The distance between the entrance and room $i$ is $x_i$ meters. Room $N+1$ is used as the parcel storage room.

Yesung has accumulated too many demerit points, so he has to deliver the parcels in the storage room. $M$ parcels are kept in the storage room, and the $j$-th parcel must be delivered to room $p_j$ and weighs $w_j$. His goal is to start from the storage room, deliver every parcel, and return to the storage room. Taking a parcel out of the storage room or putting it at its destination takes no time.

Yesung can carry any number of parcels at once with no limit. He does not have to take all the parcels at the start, and he can come back to the storage room along the way to fetch some of them. He may choose the order of deliveries freely, but he cannot leave a parcel temporarily at a place other than its destination. When Yesung carries no parcels, he moves at 1 meter per second. If the total weight of the parcels he carries is $W$, his speed drops to $\cfrac{1}{1 + W}$ meters per second.

Yesung is busy proving P=NP, so find the minimum number of seconds needed to reach the goal.

The first line contains two integers $N$ and $M$, separated by a space.

The second line contains $2N + 1$ integers $x_1, x_2, \cdots, x_{2N +1}$, separated by spaces.

From the third line onward, the next $M$ lines describe the parcels. The $j$-th of these lines contains two integers $p_j$ and $w_j$, separated by a space.

Print the answer to the problem. Under the given conditions, the answer is guaranteed to be an integer.

• $1 \leq N, M, w_j \leq 10^5$
• $1 \leq x_1 < x_2 < \cdots < x_{2N+1} \leq 3 \times 10^5$
• $1 \leq p_j \leq 2N+1$