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 ith proposal stating that the company can build a plant in city ci for cost ai.

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 ≤ i < n, the company can build power lines between cities i and i + 1 for a cost of bi, and between cities n and 1 for a cost of bn. 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 ≤ n ≤ 105) and m (1 ≤ m ≤ n), the number of cities and the number of possible locations for a power plant.

    • Then follow m lines, the ith of which contains ci (1 ≤ ci ≤ n) and ai (1 ≤ ai ≤ 109), the ith possible location for a power plant, and the cost to build it.

    • Then follows a line containing n integers bi (1 ≤ bi ≤ 109), the costs of building the power lines.

The values of c1, . . . , cm 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