Rock Garden

Vicomte de Bajteaux owns a famous collection of boulders. Until now he has kept it in the cellars of his palace, but he has decided to display the collection across his vast gardens.

The garden is a rectangle whose sides are $10^9$ units long and run east to west and north to south. For every boulder the vicomte fixed the point where it should stand, described by its distance to the southern side and its distance to the western side of the garden, and handed the two numbers to his servants. He forgot, however, to tell them in which order he had written the two distances: for some boulders he wrote the north-south distance (the ordinate, the y coordinate) first, while for others he wrote the east-west distance (the abscissa, the x coordinate) first. The servants, unaware of this, placed every boulder using the usual convention, taking the first number as the x coordinate.

To protect the collection the vicomte will surround it with a fence. For the sake of appearance the fence must be a rectangle with sides parallel to the sides of the garden, and its total length (the perimeter) must be as small as possible. A boulder may be repositioned only by interchanging its two coordinates (swapping which distance is treated as x and which as y), so the set of its two coordinate values is preserved. The rectangle may degenerate to a segment or to a single point.

The servants want to make the fence as short as possible, and among all the ways of achieving the shortest fence they want to move as little total weight as possible. Moving a boulder means interchanging its two coordinates, and it costs the weight of that boulder.

Given the current positions and weights of the boulders, determine the minimal possible fence length and the minimal total weight that must be moved to obtain a fence of that length.

The first line contains a single integer $n$ ($2 \le n \le 10^6$), the number of boulders. Each of the next $n$ lines contains three integers $x_i$, $y_i$ and $m_i$ ($0 \le x_i, y_i \le 10^9$, $1 \le m_i \le 2000$): the two current coordinates and the weight of the $i$-th boulder. No two boulders share the same unordered pair of coordinates.

Print two integers separated by a single space: the minimal possible total length (perimeter) of the fence, and the minimal total weight of the boulders whose two coordinates must be interchanged in order to achieve that length.