410064: GYM103934 L Cris's vacations in Cairo

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Cris's vacations in Cairotime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

After a semester of hard work, Cris took some days off and decided to spend them in Cairo, Egypt. The money she took there is all in Brazilian reals and US dollars, hence she usually has to do exchange operations between Egyptian pounds and these currencies.

The exchange operations that Cris does can be described by an integer $$$X$$$. If $$$X > 0$$$, she sells $$$X$$$ (dollar or real) coins for Egyptian pounds. If $$$X < 0$$$, she buys $$$X$$$ (real or dollar) coins using Egyptian pounds. If $$$X = 0$$$, she does nothing. We call profit the result of the exchange operation in Egyptian pounds. Notice that, when the exchange operation is buying (dollar or real) coins, the profit is a negative value.

Cris got access to the exchange values of the next $$$n$$$ days of a currency exchange house in Alexandria. In the $$$i$$$-th day, the dollar value in Egyptian pounds is $$$d_i$$$ and the Brazilian real value in Egyptian pounds is $$$r_i$$$. In this currency exchange house, the exchange value is the same for selling and buying Egyptian pounds. This is, if in a given day the Brazilian real value is 5 Egyptian pounds, then it's possible to sell 10 reals for 50 Egyptian pounds and it's also possible to buy 10 reals with 50 Egyptian pounds.

Since the currency exchange house is not in the city where Cris is living, she uses her visits to that other city to make the exchange operations that she needs. However, she doesn't want to spend more that one day with the bureaucracy of such transactions. Therefore, if she were to visit Alexandria between days $$$s$$$ and $$$e$$$, she just will do exchange operations in exactly one of those days.

Choosing a day that would maximize the profit of the transactions is a simple task for Cris but, due to her vacations, she asked you to answer $$$q$$$ queries of this kind for her

  • $$$s$$$ $$$e$$$ $$$D$$$ $$$R$$$: what is the biggest profit that could be obtain doing exchange operations of $$$D$$$ dollars and $$$R$$$ reals in exactly one day $$$i$$$, $$$s \leq i \leq e$$$.
Input

The first line has two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$).

The second line has $$$n$$$ different integers $$$d_i$$$ ($$$1 \leq d_i \leq 10^9$$$), the value of the dollar in Egyptian pounds on day $$$i$$$.

The second line has $$$n$$$ different integers $$$r_i$$$ ($$$1 \leq r_i \leq 10^9$$$), the value of the Brazilian real in Egyptian pounds on day $$$i$$$.

The next $$$q$$$ lines have queries of the form $$$s$$$ $$$e$$$ $$$D$$$ $$$R$$$ ($$$1 \leq s \leq e \leq n$$$ e $$$-10^9 \leq D, R \leq 10^9$$$) as described in the statement.

Output

Print $$$q$$$ lines, each one of these with the answer of the queries in the order they appear in the input.

ExampleInput
3 4
1 4 3
1 1 3
1 3 1 1
1 2 3 1
2 3 -1 -1
1 3 -2 0
Output
6
13
-5
-2

Source/Category

加入题单

上一题 下一题 算法标签: