J. Judicious Crime Response
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ streets in a city, numbered from $$$1$$$ to $$$n$$$. For every $$$1\leq i \leq n-1$$$, street $$$i$$$ and $$$i+1$$$ are connected by a two-way road with travel time $$$t_i$$$ units.

There is also one police station on each street. The $$$i$$$-th station is located on street $$$i$$$, has a forwarding time delay of $$$f_i$$$ units, and a response time delay of $$$r_i$$$ units.

Station $$$s$$$ receives an emergency call reporting a crime at street $$$d$$$. The receiving station then chooses one of the following actions:

  • Forward the call: If there exists a station $$$k$$$ on a higher-indexed street ($$$k \gt s$$$) with shorter response time delay, that is, $$$r_k \lt r_s$$$, station $$$s$$$ may forward the call to the nearest such station $$$k^*$$$. After a forwarding time delay of $$$f_s$$$ time units, station $$$k^*$$$ receives the forwarded call.
  • Respond to the call: After a response time delay of $$$r_s$$$ time units, a police car is dispatched from street $$$s$$$ and travels by road to street $$$d$$$, incurring the corresponding road travel time.
The total response time is the elapsed time from the initial call until a police car arrives at street $$$d$$$. All stations choose actions to minimize this time.

The city receives $$$q$$$ emergency calls of the form $$$(s,d)$$$. For each call, find the minimum total response time if station $$$s$$$ initially receives a call of a crime at street $$$d$$$.

Input
  • The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2\leq n,q\leq 2\times 10^5$$$), the number of streets $$$n$$$, and the number of queries $$$q$$$. There is one station on each street.
  • The second line contains $$$n$$$ integers $$$f_1, f_2, \cdots , f_n$$$ ($$$1\leq f_i \leq 10^9$$$), the $$$i$$$-th integer denoting the forwarding time delay $$$f_i$$$ of station $$$i$$$.
  • The third line contains $$$n$$$ integers $$$r_1, r_2, \cdots, r_n$$$ ($$$1\leq r_i \leq 10^9$$$), the $$$i$$$-th integer denoting the response time delay $$$r_i$$$ of station $$$i$$$.
  • The fourth line contains $$$n-1$$$ integers $$$t_1, t_2, \cdots, t_{n-1}$$$ ($$$1\leq t_i \leq 10^9$$$), the $$$i$$$-th integer denoting the travel time by road from street $$$i$$$ to street $$$i+1$$$.
  • The next $$$q$$$ lines contain two integers $$$s$$$ and $$$d$$$ ($$$1\leq s,d \leq n$$$), the $$$i$$$-th of these lines represents the $$$i$$$-th emergency call.
Output

$$$q$$$ lines. For each query $$$(s,d)$$$, output the minimum total response time if station $$$s$$$ first receives the call reporting a crime at street $$$d$$$.

Example
Input
5 5
4 7 10000 2 6
9 6 8 10000 1
2 3 10000 6
1 5
1 3
3 4
4 5
5 1
Output
12
13
10007
3
10012
Note

There are $$$5$$$ streets and police stations, and $$$5$$$ emergency calls.

Illustration of Sample Test Case

For the first emergency call $$$(1,5)$$$, the call is initially received by station $$$1$$$ and the crime is at street $$$5$$$. There are 3 possible ways to respond to the call.

One possible sequence of events is as follows:

  1. Station $$$1$$$ forwards the call to station $$$2$$$, incurring a forwarding delay of $$$4$$$ units.
  2. Station $$$2$$$ forwards the call to station $$$5$$$, incurring a forwarding delay of $$$7$$$ units.
  3. Station $$$5$$$ incurs a response time delay of $$$1$$$ unit.
The total response time of this sequence of events is $$$4+7+1 = 12$$$ time units.

Another possible sequence of events is as follows:

  1. Station $$$1$$$ forwards the call to station $$$2$$$, incurring a forwarding time delay of $$$4$$$ units.
  2. Station $$$2$$$ incurs a response time delay of $$$6$$$ units and dispatches a police car to street $$$5$$$. The car takes $$$3+10000+6 = 10009$$$ time units to reach street $$$5$$$.
The total response time of this sequence of events is $$$4+6+10009 = 10019$$$ time units.

Lastly, the only other sequence of events is as follows:

  1. Station $$$1$$$ incurs a response time delay of $$$9$$$ units and dispatches a police car to street $$$5$$$. The car takes $$$10011$$$ units to reach street 5.
The total response time of this sequence of events is $$$9 + 10011 = 10020$$$ time units.

Therefore, the minimum total response time for the first call is $$$12$$$ units.