Generators

문제

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 $nn$ cities. The administration has surveyed the cities and proposed $mm$ of them as possible locations for a power plant, with the $ii$th proposal stating that the company can build a plant in city $c_{i}c\_i$ for cost $a_{i}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 , the company can build power lines between cities $ii$ and $i+1i+1$ for a cost of $b_{i}b\_i$, and between cities $nn$ and $11$ for a cost of $b_{n}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 $nn$ ($3\le n\le {10}^{5}3\backslash leq\; n\; \backslash leq\; 10^5$) and $mm$ ($1\le m\le n1\backslash leq\; m\; \backslash leq\; n$), the number of cities and the number of possible locations for a power plant.
• Then follow $mm$ lines, the $ii$th of which contains $c_{i}c\_i$ ($1\le c_i\le n1\; \backslash leq\; c\_i\; \backslash leq\; n$) and $a_{i}a\_i$ ($1\le a_i\le {10}^{9}1\; \backslash leq\; a\_i\; \backslash leq\; 10^9$), the $ii$th possible location for a power plant, and the cost to build it.
• Then follows a line containing $nn$ integers $b_{i}b\_i$ ($1\le b_i\le {10}^{9}1\; \backslash leq\; b\_i\; \backslash leq\; 10^9$), the costs of building the power lines.

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

출력

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

3 2
1 100
2 200
150 300 150

400

3 2
1 100
2 200
300 300 150

450