G. Great Contest
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the preparation for the UnBalloon Great Programming Contest, several coaches are testing strategies to assemble the best possible superteam.

The organizers of the event allow the formation of a superteam from a subset of $$$n$$$ available teams. Each team has four types of participants, corresponding to different skill profiles, with their quantities within team $$$i$$$ being represented by four integers $$$(a_i, b_i, c_i, d_i)$$$. To assemble a super team, the organizers can choose any subset of these teams.

After choosing a superteam, the organizers gather all participants from the selected teams and define:

  • $$$A$$$ as the total number of participants of type $$$a$$$;
  • $$$B$$$ as the total number of participants of type $$$b$$$;
  • $$$C$$$ as the total number of participants of type $$$c$$$;
  • $$$D$$$ as the total number of participants of type $$$d$$$.

Then, a training session is held with the members of the superteam, with an associated numeric penalty. The training consists of two independent stages:

  • In the first stage, participants of types $$$a$$$ and $$$b$$$ in the superteam are paired against each other for a round of confrontations. Each participant faces exactly one opponent whenever possible. At the end, exactly $$$|A - B|$$$ participants remain unmatched, which will contribute to the penalty calculation;
  • In the second stage, the same process occurs between participants of types $$$c$$$ and $$$d$$$.

Immediately after these two stages, two parameters $$$(k, l)$$$ are used to calculate the penalty of the training. The values $$$k$$$ and $$$l$$$ represent the weight of each training stage, and the penalty value is given by the sum of the contributions of both stages.

  • The contribution of the first stage is the number of participants remaining after the confrontations between types $$$a$$$ and $$$b$$$, multiplied by $$$k$$$.
  • The contribution of the second stage is the number of participants remaining after the confrontations between types $$$c$$$ and $$$d$$$, multiplied by $$$l$$$.

The coaches want to test different strategies. For this purpose, they will evaluate $$$q$$$ different pairs of weights $$$(k, l)$$$.

Your task is to help the coaches: for each pair of weights $$$(k, l)$$$, determine the maximum penalty that could be achieved by choosing a subset of the teams.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the number of teams and the number of queries.

Each of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$0 \le a_i, b_i, c_i, d_i \le 10^4$$$), describing the $$$i$$$-th team.

Each of the next $$$q$$$ lines contains two integers $$$k$$$ and $$$l$$$ ($$$0 \le k, l \le 10^4$$$), representing a pair of weights.

Output

For each of the $$$q$$$ pairs of weights, print one integer: the maximum possible penalty that can be achieved.

Examples
Input
2 3
5 3 4 1
6 1 3 4
1 1
2 0
0 3
Output
9
14
9
Input
5 4
5 10 0 3
9 3 2 3
7 4 2 2
2 8 5 6
4 12 9 8
1 1
3 1
9 2
7 4
Output
22
60
177
145