레이팅 미적용The volcanic island of Fleeland has never had a proper electric net, but finally the Biomass Alternative Power Conglomerate (BAPC) has agreed to build the island's power plants and network.
On the island's coast are its \(n\) cities. The BAPC 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?
The input consists of:
- 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,c_m\) 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