[Solution] Red-Black Pepper Codeforces Solution

E. Red-Black Pepper

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Monocarp is going to host a party for his friends. He prepared 𝑛$n$ dishes and is about to serve them. First, he has to add some powdered pepper to each of them — otherwise, the dishes will be pretty tasteless.

The 𝑖$i$-th dish has two values 𝑎𝑖$a_i$ and 𝑏𝑖$b_i$ — its tastiness with red pepper added or black pepper added, respectively. Monocarp won't add both peppers to any dish, won't add any pepper multiple times, and won't leave any dish without the pepper added.

Before adding the pepper, Monocarp should first purchase the said pepper in some shop. There are 𝑚$m$ shops in his local area. The 𝑗$j$-th of them has packages of red pepper sufficient for 𝑥𝑗$x_j$ servings and packages of black pepper sufficient for 𝑦𝑗$y_j$ servings.

Monocarp goes to exactly one shop, purchases multiple (possibly, zero) packages of each pepper in such a way that each dish will get the pepper added once, and no pepper is left. More formally, if he purchases 𝑥$x$ red pepper packages and 𝑦$y$ black pepper packages, then 𝑥$x$ and 𝑦$y$ should be non-negative and 𝑥⋅𝑥𝑗+𝑦⋅𝑦𝑗$x\cdot x_j+y\cdot y_j$ should be equal to 𝑛$n$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

For each shop, determine the maximum total tastiness of the dishes after Monocarp buys pepper packages only in this shop and adds the pepper to the dishes. If it's impossible to purchase the packages in the said way, print -1.

Input

The first line contains a single integer 𝑛$n$ (1≤𝑛≤3⋅105$1\le n\le 3\cdot {10}^5$) — the number of dishes.

The 𝑖$i$-th of the next 𝑛$n$ lines contains two integers 𝑎𝑖$a_i$ and 𝑏𝑖$b_i$ (1≤𝑎𝑖,𝑏𝑖≤109$1\le a_i,b_i\le {10}^9$) — the tastiness of the 𝑖$i$-th dish with red pepper added or black pepper added, respectively.

The next line contains a single integer 𝑚$m$ (1≤𝑚≤3⋅105$1\le m\le 3\cdot {10}^5$) — the number of shops.

The 𝑗$j$-th of the next 𝑚$m$ lines contains two integers 𝑥𝑗$x_j$ and 𝑦𝑗$y_j$ (1≤𝑥𝑗,𝑦𝑗≤𝑛$1\le x_j,y_j\le n$) — the number of servings the red and the black pepper packages are sufficient for in the 𝑗$j$-th shop, respectively.

Output

Print 𝑚$m$ integers. For each shop, print the maximum total tastiness of the dishes after Monocarp buys pepper packages only in this shop and adds the pepper to the dishes. If it's impossible to purchase the packages so that each dish will get the pepper added once and no pepper is left, print -1.