Minimum Cost to Select People for Skill Quotas

Each person has a non-negative cost and two skill flags. For K=1..n, find the minimum cost so that at least K people have skill 1 and at least K people have skill 2; a person with both skills counts toward both sides; output −1 if infeasible.

输入格式

n (1≤n≤200000), followed by n lines of cost skill1 skill2. cost is 0..10⁹, and skills are 0/1. Non-negative costs are site-added; answers use 64-bit integers.

输出格式

Output the minimum cost or −1 for K=1..n in order.

样例 1

输入：

3
5 1 1
4 1 0
4 0 1

输出：

5 13 -1

样例 2

输入：

2
3 1 0
2 0 1

输出：

5 -1

样例 3

输入：

2
0 1 1
7 1 1

输出：

0 7