ML Models Feature Compatibility (k-capable)

Each model has a positive cost and a two-bit feature string 00/01/10/11. For each k=1..n, choose a set of models such that each of the two features is supported by at least k models, and find the minimum total price; the same model cannot be bought more than once.

输入格式

The first line contains n, followed by n lines of cost feature. 1≤n≤1000, 1≤cost≤10000.

输出格式

First output n, then output the n answers; output −1 for an impossible k.

样例 1

输入：

6
3 10
6 01
9 11
1 01
2 11
5 10

输出：

6
2 6 15 26 -1 -1

样例 2

输入：

2
1 00
5 10

输出：

2
-1 -1

样例 3

输入：

3
10 11
2 01
3 10

输出：

3
5 15 -1

样例说明

The results are [2,6,15,26,−1,−1], [−1,−1], and [5,15,−1], respectively.