시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 4 4 100.000%

문제

The volcanic island of Fleeland has never had a proper electric net, but finally the administration of the island have agreed to build the island's power plants and network.

On the island's coast are its $n$ cities. The administration has surveyed the cities and proposed $m$ of them as possible locations for a power plant, with the $i$th proposal stating that the company can build a plant in city $c_i$ for cost $a_i$.

These power plants are very modern and a single plant could power the whole island, but the volcano makes building power lines across the island a dangerous affair. For $1 \leq i < n$, the company can build power lines between cities $i$ and $i+1$ for a cost of $b_i$, and between cities $n$ and $1$ for a cost of $b_n$. A city will receive power if it contains a power plant or is connected to a city with a power plant via power lines.

What is the cheapest way to power all the cities on the island?

입력

  • One line containing two integers $n$ ($3\leq n \leq 10^5$) and $m$ ($1\leq m \leq n$), the number of cities and the number of possible locations for a power plant.
  • Then follow $m$ lines, the $i$th of which contains $c_i$ ($1 \leq c_i \leq n$) and $a_i$ ($1 \leq a_i \leq 10^9$), the $i$th possible location for a power plant, and the cost to build it.
  • Then follows a line containing $n$ integers $b_i$ ($1 \leq b_i \leq 10^9$), the costs of building the power lines.

The values of $c_{1,\ldots,n}$ are unique and given in strictly increasing order.

출력

Output the minimal cost of powering all cities on the island.

예제 입력 1

3 2
1 100
2 200
150 300 150

예제 출력 1

400

예제 입력 2

3 2
1 100
2 200
300 300 150

예제 출력 2

450