Team Selection Without Adjacent Skills

You are given N players numbered from \(1\) to \(N\). The \(i\)th player has an age \(age_i\) and a skill value \(skill_i\). The excellence of a team is defined as the sum of the skill values of the players included in the team. However, you believe that placing two players with similar skills on the same team will lead to conflicts.

Two players \(x\) and \(y\) are considered to have similar skills if and only if there does not exist a third player \(z\) such that \[ skill_x < skill_z < skill_y \] (i.e. they are consecutive in the global ordering by skill, regardless of any other attributes).

You need to form teams to participate in \(T\) matches. Each match comes with an age limit \(A\) and a maximum team size \(K\). For a match, only players with \(age_x \le A\) are eligible. Furthermore, the team you form can include at most \(K\) players and must not contain any two players with similar skills (as defined above). A player can participate in multiple matches independently.

Your task is to help determine, for each match, the maximum possible excellence (i.e. sum of skills) you can achieve by selecting a subset of eligible players (subject to the constraints) for that match.

inputFormat

The input begins with a line containing two integers \(N\) and \(T\) indicating the number of players and the number of matches.

The next \(N\) lines each contain two integers \(age_i\) and \(skill_i\) representing the attributes of the \(i\)th player.

The following \(T\) lines each contain two integers \(A\) and \(K\), indicating the age limit and the maximum team size for that match.

outputFormat

For each match, output a single integer on a separate line: the maximum total skill sum that can be achieved by selecting a valid team (a subset that does not include two players with similar skills and has at most \(K\) players) among those with \(age \le A\).

sample

3 2
5 10
3 5
4 7
5 2
3 2

15
5