시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4.5 초 | 1024 MB | 14 | 1 | 1 | 9.091% |
There are $n$ bus stations and $n$ bus lines along the main street of City A. The bus stations are labeled from $1$ to $n$ from left to right, and the importance of station $i$ is $a_i$. The bus lines are also numbered from $1$ to $n$. A bus of line $k$ stops at stations whose importance is greater than or equal to $k$. Each bus line operates in both directions.
A tourist standing at station $x$ can take any bus that stops at station $x$, pick a direction, and go to the next station $y$ visited by that bus in that direction (of course, it is only possible if such station exists). The cost of such trip is $l_x$ yuan if $y < x$, or $r_x$ yuan if $y > x$. Tourists can take multiple bus trips to reach their destination.
Now there are $q$ tourists, and the $j$-th tourist wants to travel from station $s_j$ to station $t_j$. Your task is to find the minimum cost of the route for each tourist.
It is guaranteed that, for each $i$ from $1$ to $n - 1$, the following are true: $l_{i} \le l_{i + 1}$ and $r_{i} \ge r_{i + 1}$.
The first line of input contains a single integer $T$, the number of test cases ($1 \le T \le 3 \cdot 10^4$). The descriptions of test cases follow.
The first line of each test case contains two integers $n$ and $q$: the number of stations and the number of tourists ($1 \le n, q \le 3 \cdot 10^5$).
The second line contains $n$ integers $a_1, \ldots, a_n$, where $a_i$ is the importance of station $i$ ($1 \le a_i \le n$).
Then follow $n$ lines, the $i$-th of which contains two integers $l_i$ and $r_i$: the costs at station $i$ ($1 \le l_i, r_i \le 10^9$, $l_{i} \le l_{i + 1}$, $r_{i} \ge r_{i + 1}$).
Then follow $q$ lines, the $j$-th of which contains two integers $s_j$ and $t_j$: the endpoints of a route for $j$-th tourist ($1 \le s_j, t_j \le n$).
The sum of $n$ and the sum of $q$ over all test cases do not exceed $3 \cdot 10^5$.
For each tourist, output a line with the answer.
1 9 6 1 7 3 4 9 9 1 2 2 1 11 1 11 5 11 7 10 8 6 8 4 8 3 9 1 10 1 1 9 5 1 3 1 7 6 2 6 1 1
33 9 6 8 17 0