기숙사 택배물 배달

한국과학영재학교 기숙사에는 기숙사 입구와 $2N + 1$개의 방이 일직선으로 배치되어 있다. 왼쪽에서 $i$번째 방이 $i$번 방이고, 기숙사 입구는 $1$번 방 왼쪽에 있다. 입구와 $i$번 방 사이의 거리는 $x_i$미터이다. 그중에서, $N+1$번 방은 택배물 보관실로 사용되고 있다.

예성이는 벌점이 너무 많이 쌓여서 택배물 보관실의 택배물들을 배달하게 되었다. $M$개의 택배물이 택배물 보관실에 보관되어 있고, $j$번째 택배물은 $p_j$번 방으로 배달되어야 하며 무게는 $w_j$이다. 예성이의 목표는 택배물 보관실에서 출발해 모든 택배물을 배달한 후 다시 택배물 보관실로 돌아오는 것이다. 예성이가 택배물 보관실에서 택배물을 꺼내거나 택배물을 목적지에 놓을 때는 시간이 걸리지 않는다.

너무나도 강력한 예성이는 한 번에 여러 개의 택배물을 제한 없이 들 수 있지만, 처음에 모든 택배물을 가지고 출발할 필요는 없고, 일부는 보관실에 도중에 다시 들러서 꺼내올 수도 있다. 또 택배물을 배달하는 순서는 자유롭게 정할 수 있지만, 배달되어야 하는 목적지 이외의 장소에 잠시 놓아둘 수는 없다. 예성이가 택배물을 들고 있지 않을 때의 이동 속도는 초속 $1$미터인데, 현재 가지고 있는 택배물 무게의 총합이 $W$일 때는 이동 속도가 초속 $\cfrac{1}{1 + W}$미터로 감소한다.

예성이는 P=NP 문제를 증명하느라 시간이 없으므로, 목표를 달성하기 위해 최소 몇 초가 걸리는지 구해주자.

첫 번째 줄에 두 정수 $N, M$이 공백을 사이에 두고 주어진다.

두 번째 줄에 $2N + 1$개의 정수 $x_1, x_2, \cdots, x_{2N +1}$가 공백을 사이에 두고 주어진다.

세 번째 줄부터 $M$개의 줄에 택배물들의 정보가 주어지며, 그 중 $j$번째 줄에는 두 정수 $p_j$와 $w_j$가 공백을 사이에 두고 주어진다.

문제의 정답을 출력한다. 주어진 조건 하에서 정답은 정수임이 보장된다.

• $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$