발전소

화산섬 플리랜드에는 제대로 된 전력망이 한 번도 없었다. 그러나 마침내 섬의 행정부가 섬의 발전소와 전력망을 건설하기로 합의했다.

섬의 해안에는 $n$개의 도시가 있다. 행정부는 도시들을 조사하여 그중 $m$곳을 발전소를 지을 수 있는 후보지로 제안했고, $i$번째 제안은 $c\_i$번 도시에 $a\_i$의 비용으로 발전소를 지을 수 있다는 내용이다.

이 발전소는 매우 현대적이어서 발전소 하나로 섬 전체에 전력을 공급할 수 있지만, 화산 때문에 섬을 가로지르는 전선을 놓는 일은 위험하다. $1 \leq i < n$인 $i$에 대해 $i$번 도시와 $i+1$번 도시 사이에 $b\_i$의 비용으로 전선을 놓을 수 있고, $n$번 도시와 $1$번 도시 사이에는 $b\_n$의 비용으로 전선을 놓을 수 있다. 어떤 도시에 발전소가 있거나, 전선으로 발전소가 있는 도시와 연결되어 있으면 그 도시는 전력을 공급받는다.

섬의 모든 도시에 전력을 공급하는 가장 저렴한 방법은 무엇인가?

• 첫 줄에 두 정수 $n$ ($3\leq n \leq 10^5$)과 $m$ ($1\leq m \leq n$)이 주어진다. 각각 도시의 수와 발전소를 지을 수 있는 후보지의 수이다.
• 이어서 $m$개의 줄이 주어지고, 그중 $i$번째 줄에는 $c\_i$ ($1 \leq c\_i \leq n$)와 $a\_i$ ($1 \leq a\_i \leq 10^9$)가 주어진다. 각각 $i$번째 발전소 후보지와 그 발전소를 짓는 비용이다.
• 그다음 줄에는 $n$개의 정수 $b\_i$ ($1 \leq b\_i \leq 10^9$)가 주어진다. 전선을 놓는 비용이다.

$c\_{1,\ldots,n}$의 값은 서로 다르며 엄격히 증가하는 순서로 주어진다.

섬의 모든 도시에 전력을 공급하는 최소 비용을 출력한다.