Maximizing Crystal Value Without Resonance

A hexagon‐tiled map is given where each cell is a hexagon with six neighbors. Every cell is identified by a triplet of integers \((x,y,z)\) but note that many coordinate triplets may refer to the same cell. In fact, any two triplets of the form \((x,y,z)\) and \((x+ k, y+ k, z+ k)\) (for any integer \(k\)) describe the same cell.

There are \(N\) crystals placed on the map. The \(i\)th crystal is placed in the cell represented by \((x_i,y_i,z_i)\) and has a base value \(c_i\). (A cell might initially contain several crystals.)

Certain cells have an energy source. In particular, if a cell (for any representative coordinates) has \(x+y+z\) divisible by \(3\) then that cell is equipped with an energy source. In an energy‐equipped cell every crystal’s value is increased by \(10\%\); that is, its contribution becomes \(1.1\times c_i\).

However, if three crystals remain in cells that have the following arrangements, a dangerous resonance will occur:

• Type \(a\) resonance: Three crystals placed in three cells that form a triangle – that is, every pair of the three cells are adjacent. (Two cells are adjacent if one’s coordinates can be obtained from the other by adding one of the six vectors \((1,0,0)\), \((-1,0,0)\), \((0,1,0)\), \((0,-1,0)\), \((0,0,1)\), or \((0,0,-1)\) – after canonicalization.)
• Type \(b\) resonance: Three crystals placed in cells that lie consecutively along a straight line. In other words, if cells \(A\), \(B\), and \(C\) are such that \(A\) is adjacent to \(B\), \(B\) is adjacent to \(C\), the step direction from \(A\) to \(B\) is the same as from \(B\) to \(C\), and additionally cell \(B\) (the middle cell) has an energy source, then these three crystals trigger a type \(b\) resonance.

Your task is to remove some of the crystals (possibly none) so that no resonance (of either type) occurs among the remaining crystals while maximizing the total value of the remaining crystals.

Note: Since the resonance condition is determined solely by which cells have at least one crystal remaining, and a cell’s total value is the sum of the values of all crystals in that cell (with the energy bonus applied if applicable), it is always optimal to either keep all crystals in a cell or remove all of them.

Coordinate Canonicalization

The coordinates \((x,y,z)\) are not unique. In fact, any two coordinates of the form \((x,y,z)\) and \((x+k, y+k, z+k)\) represent the same cell. We define a canonical representation for a cell as follows: given a cell \((x,y,z)\), let \(s=x+y+z\) and let \(r\) be the residue of \(s\) modulo \(3\) (i.e. \(r\in\{0,1,2\}\)). Then the canonical representative is defined as \[ \Bigl(x-\frac{s-r}{3},\; y-\frac{s-r}{3},\; z-\frac{s-r}{3}\Bigr), \] so that the sum of the coordinates is exactly \(r\). In particular, a cell is equipped with an energy source if and only if its canonical representative satisfies \(x+y+z\equiv0\pmod{3}\).

inputFormat

The first line contains a single integer \(N\) (the number of crystals). Each of the following \(N\) lines contains four integers \(x_i\), \(y_i\), \(z_i\) and \(c_i\), representing the coordinates of a crystal and its value, respectively.

outputFormat

Output a single number representing the maximum total value of the remaining crystals (after the appropriate 10% bonus is applied in energy‐cells) so that no resonance occurs. Print the answer as a floating–point number with at least one digit after the decimal point.

sample

3
0 0 0 100
1 0 0 100
0 1 0 100

310.0