21st National Assembly Election

Given the constituency seat count and the proportional vote count of each party, compute the total number of seats each party wins in the 21st National Assembly election. The Assembly has $300$ seats in total: $253$ constituency members and $47$ proportional members.

Proportional seats are allocated only to parties that won at least 3% of the valid proportional votes or won 5 or more constituency seats (the threshold clause). A party that receives proportional seats is called a seat-allocating party. For the 21st National Assembly election only, proportional seats are allocated as follows.

Step 1: allocate 30 seats by nationwide semi-linked method (linkage ratio 50%)

For each seat-allocating party, take the seat count from its proportional vote share, subtract the number of constituency winners of that party, and allocate proportional seats to that party first until the result reaches 50% of that difference.

$\frac{\left(N-R\right)\times p_i - r_i}{2}$

($N$: total number of Assembly seats, $R$: total constituency winners of parties that are not seat-allocating parties plus independent constituency winners, $p_i$: the proportional vote share of party $i$, $r_i$: the constituency winners of party $i$)

$p_i$ is not the share of all valid votes. It is recalculated by dividing the votes of the party by the total votes of all seat-allocating parties.

If the result is less than 1, it is 0. Otherwise, round to the nearest integer. The resulting integer is called the linked seat count $s_i^\prime$.

If the sum of $s_i$ equals 30, that count is confirmed as the proportional seat count $s_i$ of each party for the 30 of 47 seats.

Step 2-1: if the sum of linked seat counts is less than 30

If the seats allocated in Step 1 total less than 30, the remaining seats are allocated by the existing proportional method according to each party's proportional vote share.

$s_i^\prime + \left(30-\sum s^\prime \right) \times p_i$

($p_i$: the proportional vote share of party $i$)

Allocate the integer part first. Then allocate the rest in descending order of the fractional part until the total linked seat count reaches 30. The resulting seat count of each party is the adjusted proportional seat count $s_i$ for the 30 of 47 seats.

Step 2-2: if the sum of linked seat counts is greater than 30

If the seats allocated in Step 1 exceed 30, reallocate them in proportion to each party's linked seat count.

$\frac{30 \times s_i^\prime}{\sum s^\prime}$

Allocate the integer part first. Then allocate the rest in descending order of the fractional part until the total linked seat count reaches 30. The resulting seat count of each party is the adjusted proportional seat count $s_i$ for the 30 of 47 seats.

Step 3: allocate 17 seats by the existing proportional method

Allocate the remaining 17 seats according to each party's proportional vote share.

$17 \times p_i$

($p_i$: the proportional vote share of party $i$)

Allocate the integer part first. Then allocate the rest in descending order of the fractional part until the count reaches 17. The resulting seat count of each party is the proportional seat count $t_i$ for the 17 of 47 seats.

The final proportional seat count of party $i$ is $s_i + t_i$. Adding the constituency seat count $r_i$ gives the total seats party $i$ holds in the 21st National Assembly: $s_i+t_i+r_i$.

The first line contains the number of parties $P$ that fielded candidates and the total number of voters $V$. ($1 \leq P \leq 50$), ($1 \leq V \leq 10^9$)

Each of the next $P$ lines contains a party name, its constituency seat count, and its proportional vote count in the National Assembly election. A party name consists of up to 50 lowercase English letters and underscores (_). Party names are unique.

The sum of constituency seats does not exceed 253. The sum of proportional votes does not exceed $V$.

Print each party and its total seats in the 21st National Assembly, sorted by seat count in descending order. If two parties have the same seat count, print the party whose name comes first in lexicographic order first.

The rules of the Public Official Election Act (Act No. 16864) enforced on January 14, 2020 apply, with the following exception.

• When seats are allocated in descending order of the fractional part, and two fractional parts are exactly equal, the party with the smaller ballot number is allocated first. (The election act says such ties are decided by lot.)

It is guaranteed that at least one party has $s_i^\prime>0$.