기숙사 택배물 배달

한국과학영재학교 기숙사에는 기숙사 입구와 $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$