Don't panic, today's problems were not set by Xiaoqiang. "A work infused with countless efforts, yet now I have to destroy it with my own hands. It's hard to understand his feelings." "There is no other way. If the energy resonance is not eliminated..." Looking at the crystals already rigged with explosives, 02 put down the binoculars and looked at the resonance analysis report in her hand. There will still be some crystals that survive... perhaps.

The map consists of a tiling of hexagonal cells, where each cell is adjacent to six others. For convenience, we describe the position of a cell using coordinates $(x, y, z)$, representing the location reached after taking a certain number of steps in the $x, y, z$ directions from the origin, as shown in the figure. It is possible for two different coordinates to describe the same cell; for example, $(1, 1, 1)$ and $(0, 0, 0)$ both describe the origin.

Clearly, the cell $(x, y, z)$ is adjacent to $(x+1, y, z)$, $(x-1, y, z)$, $(x, y+1, z)$, $(x, y-1, z)$, $(x, y, z+1)$, and $(x, y, z-1)$. There are $N$ crystals located in the cells of the map. The $i$-th crystal is located in the cell represented by coordinates $(x_i, y_i, z_i)$ and has a value of $c_i$. Multiple crystals may exist within a single cell. Some cells in the map are equipped with energy sources. As shown in the figure below, energy sources are installed in any cell where the coordinates satisfy the condition that $x+y+z$ is a multiple of $3$.

The value of any crystal in a cell with an energy source increases by an additional $10\%$. If the cells containing three crystals are arranged in a specific configuration, they will trigger a resonance. There are two types of resonance: a-resonance and b-resonance.

a-resonance: If the cells containing three crystals are pairwise adjacent and form a triangle, an a-resonance is triggered.

Each triangle in the figure indicates that the three crystals in these cells will trigger an a-resonance.

b-resonance: If the cells containing three crystals are arranged in a line of length 2 (i.e., they are adjacent in a sequence) and the middle cell contains an energy source, a b-resonance is triggered.

In the figure, the pink line segments indicate that the three crystals in these cells will trigger a b-resonance, while the black line segments indicate that no b-resonance will occur even if these three cells contain crystals.

You must now destroy some crystals such that no resonance occurs, while maximizing the total value of the remaining crystals.

Input

The first line contains a positive integer $N$, representing the number of crystals.

The next $N$ lines each contain four integers $x_i, y_i, z_i, c_i$, separated by spaces, representing the position and value of a crystal.

Crystal positions may overlap.

Output

A single line containing a real number, representing the maximum total value of the remaining crystals. Round to one decimal place.

Examples

Input 1

4
0 0 0 11
1 0 0 5
0 1 0 7
0 0 -1 13

Output 1

25.1

Note 1

The four crystals form a rhombus. There is no b-resonance, but there are 2 a-resonances: the triangles formed by crystals (1, 2, 4) and (1, 3, 4). Therefore, to eliminate both a-resonances, there are 3 possible schemes:

1. Destroy crystal 1, keep crystals 2, 3, 4. Total remaining value: $5 + 7 + 13 = 25$.
2. Destroy crystal 4, keep crystals 1, 2, 3. Total remaining value: $11 \times (1 + 10\%) + 5 + 7 = 24.1$.
3. Destroy crystals 2 and 3, keep crystals 1 and 4. Total remaining value: $11 \times (1 + 10\%) + 13 = 25.1$.

Thus, we choose the third scheme, and the maximum total remaining value is $25.1$.

Subtasks

For $30\%$ of the data, $N \le 20$.

For $60\%$ of the data, $N \le 100$.

For $90\%$ of the data, $N \le 300$.

For $100\%$ of the data, $N \le 50\,000$, $1 \le c_i \le 1\,000$, $|x_i|, |y_i|, |z_i| \le 1\,000$.