#213428. [CEOI 2025] highest

In an alternate universe, Vlad is stuck inside a futuristic version of the Poenari Fortress, now spanning floors, numbered through . From each floor (), he can only go up, either by taking the stairs and paying drop of blood (this is the currency that vampires use to pay in Romania), or by turning into a bat and traversing the vents, for which he has to pay drops of blood. The stairs can take him up to floors upwards, while the vents span up to floors upwards, where and are two given arrays: and .

Formally, from floor (), Vlad can go:

• anywhere from floor to floor without exceeding , for a cost of
• anywhere from floor to floor without exceeding , for a cost of

Furthermore, his brothers Radu and Mircea proposed scenarios for Vlad, each one consisting of two floors and (). Vlad has to answer their questions: what is the least amount of blood that he has to sacrifice to get from floor to floor ?

Implementation Details

You will have to implement the function solve:

std::vector<int> solve(std::vector<int> &v, std::vector<int> &w, std::vector<std::pair<int,int>> &queries);

• Receives the vectors , the heights of the flights of stairs, and , the heights of the vent systems, starting at each floor, both of them of size .
• Also receives the queries, a vector of pairs of size . Each pair contains and as described in the statement.
• Returns a vector of size , consisting of the answers to the queries.

样例输入 1

7
2 3 1 1 1 1 2
3 4 1 2 1 2 2
3
0 4
0 5
0 6

样例输出 1

2
3
4

样例输入 2

10
1 1 1 2 3 2 1 1 2 3 
2 4 1 4 1 4 1 3 2 3 
5
3 9
0 9
0 7
0 4
3 5

样例输出 2

3
5
4
3
1

Sample Explanation 1

Consider the following call:

solve({2, 3, 1, 1, 1, 1, 2}, {3, 4, 1, 2, 1, 2, 2}, {{0, 4}, {0, 5}, {0, 6}})

Here we have and queries, and .

For the first query , Vlad has to make two -cost jumps: to (even though he can jump to , floor will then take him further), then to . Total cost: .

For the second query , there are optimal paths: to (cost ), to (cost ), to (cost ); the second path is to (cost ), to (cost ). Total cost: .

For the third query , one example path of cost is to (cost ), to (cost ), to (cost ). Total cost: .

So the vector that the function will return must be:

Sample Explanation 2

Consider the following call:

solve({1, 1, 1, 2, 3, 2, 1, 1, 2, 3}, {2, 4, 1, 4, 1, 4, 1, 3, 2, 3}, {{3, 9}, {0, 9}, {0, 7}, {0, 4}, {3, 5}})

These are the optimal paths for the queries:

• : to (cost ), to (cost ) total:
• : to (cost ), to (cost ), to (cost ) total:
• : to (cost ), to (cost ), to (cost ) total:
• : to (cost ), to (cost ) total:
• : to (cost ) total:

So the vector that the function will return must be:

Constraints

• for all
• for all queries

Subtasks

1. (5 points)
2. (7 points)
3. (11 points)
4. (44 points)
5. (8 points) and for all
6. (25 points) No further restrictions