P15497 [ICPC 2025 APC] Hold the Star

You are playing a computer game with $n$ rooms, $m$ characters, and one star. The rooms are arranged from left to right and numbered from $1$ to $n$ in that order. The characters are numbered from $1$ to $m$. At any time, each character is in one of the rooms and the star is either in one of the rooms or held by one of the characters. The objective of the game is for the star to be held by character $m$. You can play the game by performing several actions. Each action costs a certain amount of staracips (the unit of currency in the game), possibly zero. In each action, you choose a character $x$ (let room $y$ be the room the character is currently in) and command the character to do either of the following: - Move to one of the adjacent rooms ($y - 1$ or $y + 1$), if such a room exists. If character $x$ is holding the star, then the character continues to hold the star. This action costs $s_x$ staracips. The values of $s_1, s_2, \ldots, s_m$ are given. - Pick the star up and hold it, if the star is currently in room $y$ and is not held by any character. This action costs $0$ staracips. - Put the star down and release it, if the star is currently held by character $x$. The star then falls to room $y$. This action costs $0$ staracips. The game contains $q$ levels, numbered from $1$ to $q$. In all levels, each character $i$ is initially in room $r_i$ and character $m$ must hold the star to win the level. The only difference between the levels is that, in each level $j$, the star is initially in room $l_j$. For each level, you want to compute the minimum total staracips you have to spend to win the level. Note that you don’t have to minimize the number of actions.

The first line of input contains three integers $n$, $m$, and $q$ ($1 \leq n \leq 10^9$; $1 \leq m \leq 100\,000$; $1 \leq q \leq 100\,000$). The $i$-th of the next $m$ lines contains two integers $r_i$ and $s_i$ ($1 \leq r_i \leq n$; $1 \leq s_i \leq 10^9$). The $j$-th of the next $q$ lines contains an integer $l_j$ ($1 \leq l_j \leq n$).

For each level in order, output the minimum total staracips you have to spend to win the level.

**Explanation for the sample input/output #1** You can win the first level by spending $5$ staracips by doing the following actions: 1. Character $5$ moves from room $2$ to room $1$. This action costs $5$ staracips. 2. Character $5$ picks the star up. You can win the second level by spending $0$ staracips by doing the following actions: 1. Character $5$ picks the star up. You can win the third level by spending $8$ staracips by doing the following actions: 1. Character $4$ picks the star up. 2. Character $4$ moves from room $5$ to room $4$. This action costs $3$ staracips. 3. Character $4$ moves from room $4$ to room $3$. This action costs $3$ staracips. 4. Character $4$ puts the star down. 5. Character $2$ picks the star up. 6. Character $2$ moves from room $3$ to room $2$. This action costs $2$ staracips. 7. Character $2$ puts the star down. 8. Character $5$ picks the star up. You can win the fourth level by spending $14$ staracips by doing the following actions: 1. Character $2$ moves from room $3$ to room $4$, then to room $5$, then to room $6$. These actions cost $3 \times 2 = 6$ staracips in total. 2. Character $2$ picks the star up. 3. Character $2$ moves from room $6$ to room $5$, then to room $4$, then to room $3$, then to room $2$. These actions cost $4 \times 2 = 8$ staracips in total. 4. Character $2$ puts the star down. 5. Character $5$ picks the star up.