[POI2007] SKA-Rock Garden

题目描述

Blue Mary是一个有名的石头收藏家。迄今为止，他把他的藏品全部放在他的宫殿的地窖中。现在，他想将他的藏品陈列在他的花园中。皇家花园是一个边长为1000000000单位的平行于坐标轴的正方形。对于每个石头，Blue Mary都有一个他想放置的坐标，然后将他告诉他的属下。不幸的是，他忘了告诉他们坐标的顺序（比如无法分辨(x,y)和(y,x)）。属下们，就自己决定了每个石头的具体位置。为了保护他的藏品，Blue Mary决定建造一个篱笆来保护他们。为了美学的需要，篱笆也被设计为平行于坐标轴的矩形。如果花园的布局知道了，那么就可以知道最短长度的篱笆的布局。他的属下们需要变换石头的坐标使得篱笆的长度最少。每个石头只能从(x,y)变换为(y,x)，由于每个石头的重量不一样。属下们希望他们移动的石头的重量和最少。

输入格式

The first line of the standard input contains a single integer $n$ ($2 \le n \le 1\ 000\ 000$), denoting the number of boulders in the collection. The following $n$ lines contain three integers $x_i$, $y_i$ and $m_i$ each ($0 \le x_i, y_i \le 1\ 000\ 000\ 000$, $1 \le m \le 2000$), separated by single spaces, denoting the present coordinates and the weight of $i$'th boulder. No unordered pair of coordinates will appear in the input more than once.

输出格式

The first line of the standard output should contain two integers, separated by a single space - the minimal length of fence possible and the minimal weight of the boulders to be moved in order to obtain such a length.

The second line should contain a sequence of $n$ zeros and/or ones - $i$'th element of the sequence should be a one if in the optimal solution the $i$'th boulder is to be moved and zero otherwise. Should more than one correct solutions exist, your programme is to write out any one of them.

样例 #1

样例输入 #1

5
2 3 400
1 4 100
2 2 655
3 4 100
5 3 277

样例输出 #1

10 200
01010