Determining Medal Threshold Boundaries in ICPC

In ICPC contests, teams are ranked according to two parameters: the number of problems solved and the total penalty time. A team's score is represented as a pair \((s, t)\) where s is the number of problems solved and t is the penalty time. The ranking order is defined as follows:

• A score \((s_1, t_1)\) is considered better than \((s_2, t_2)\) if either \(s_1 > s_2\), or \(s_1 = s_2\) and \(t_1 < t_2\).

In a typical contest, medals (gold, silver, bronze, and honorable mention) are awarded to teams in segments of the ranking list. For each medal type, a medal threshold is defined as a score \(X\) (which must be achievable, i.e. exactly equal to some team's score) such that all teams with score \(\ge X\) receive that medal, and those with a score lower than \(X\) do not. Due to tie cases, there might be several possible achievable thresholds that yield the desired medal count. We define the upper bound (supremum) and the lower bound (infimum) for the set of all valid medal thresholds for each medal category.

More formally, suppose the contest has n teams. After sorting the teams in non‐increasing order (i.e. by descending number of solved problems, and if tied, by ascending penalty time), assume that the medal counts for gold, silver, bronze and honorable mention are given as \(G, S, B, H\) respectively (with \(G+S+B+H=n\)). For a given medal category with count \(k\), let the teams receiving that medal be those with indices from c to c+k-1 (0-indexed). Denote \(L\) as the score of the last team in that medal category and \(U\) as the score of the team immediately after that category (if one exists). A score \(X\) (which must coincide with some team's score) is a valid threshold for that medal category if it satisfies:

[ U \prec X \preceq L ]

where \(\prec\) denotes the ranking order (i.e. \(X\) is strictly worse than any score that beats it). The problem is to compute, for each medal category, the supremum and infimum of the set of valid thresholds. In our setting, if no valid threshold exists for a medal, output -1 -1 -1 -1 for that medal.

Note: For any medal category with a count of zero, consider that no threshold exists and output -1 -1 -1 -1.

inputFormat

The input consists of:

1. A line containing an integer n (\(1 \le n \le 10^5\)) representing the number of teams.
2. n lines follow, each containing two integers \(s\) and \(t\) where \(0 \le s \le 15\) and \(0 \le t < 300\). Here, s is the number of problems solved and t is the penalty time.
3. A final line with four integers: G S B H (\(G, S, B, H \ge 0\) and \(G+S+B+H=n\)), representing the medal counts for gold, silver, bronze, and honorable mention respectively.

Teams are to be sorted in non‐increasing order: by descending s and, in the case of a tie, by ascending t.

outputFormat

Output four lines. Each line corresponds to one medal category in the order: gold, silver, bronze, honorable mention. For each medal, if a valid threshold exists, output four integers: the supremum's s and t followed by the infimum's s and t (separated by spaces). If no valid threshold exists for that medal, output -1 -1 -1 -1 on that line.

sample

5
3 50
3 40
2 100
2 90
1 20
1 2 1 1

3 40 3 40
2 90 2 90
2 100 2 100
1 20 1 20