BAPC20-095.\problemyamlname

Medium · 1 s · 256 MB

icpc
bapc
2020

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?

Giriş formatı

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.

Çıxış formatı

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

Qeyd

Source: Benelux Algorithm Programming Contest 2020 · Author: Timon Knigge · License: CC BY-SA 4.0 · Original: https://bapc.eu · Statement adapted for AlgoLens and shared under the same license. · 5 of the 15 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

3 2
1 100
2 200
150 300 150

Çıxış #1

Giriş #2

3 2
1 100
2 200
300 300 150

Çıxış #2