MC Matthew and Demolition Dan are playing their favorite Lego style adventure game! To spice up their vanilla crafting experience, they decided to add a mod enabling the creation of custom TNT. Matthew has placed $N$ pieces of modded TNT, which we will consider as singular points $(x_i, y_i, z_i)$, in his world. Each piece of TNT has a volatility constant of $v_i$ (not necessarily an integer), which is proportional to how powerful of a blast it can produce and how sensitive it is to disturbances in its surroundings (namely other TNT exploding). Demolition Dan has been challenged by MC Matthew to place a single piece of TNT to trigger all of the pre-placed TNT *at the same time* (this means that Dan cannot use chain reactions to trigger some subset of Matthew's TNT, which will then subsequently trigger the rest of the already placed TNT). Note that Dan does not necessarily need to choose a lattice point as his location for placement, and multiple pieces of TNT can be placed at the same coordinates.
If Dan places TNT at $(x, y, z)$, and one of Matthew's TNT pieces is at $(x_i, y_i, z_i)$, then the volatility of Dan's TNT must be at least
The higher the volatility constant of TNT, the more expensive it is to craft it. Can you help Dan find the position for his TNT that minimizes the volatility required, and output that volatility constant?
The first line of input will contain a single integer $N$ ($1 <= N <= 20000$), the number of pieces of TNT that MC Matthew has placed down. The next $N$ lines of input will contain four space separated integers $x_i$, $y_i$, $z_i$, and $v_i$ ($0 <= x_i, y_i, z_i <= 10^6$, $1 <= v_i <= 10^6$) representing the coordinates of a TNT piece and its volatility.
Output the minimum volatility constant necessary to complete the detonation. Answers with a relative or absolute error of at most $10^(− 6)$ will be considered correct.
## Input
The first line of input will contain a single integer $N$ ($1 <= N <= 20000$), the number of pieces of TNT that MC Matthew has placed down. The next $N$ lines of input will contain four space separated integers $x_i$, $y_i$, $z_i$, and $v_i$ ($0 <= x_i, y_i, z_i <= 10^6$, $1 <= v_i <= 10^6$) representing the coordinates of a TNT piece and its volatility.
## Output
Output the minimum volatility constant necessary to complete the detonation. Answers with a relative or absolute error of at most $10^(− 6)$ will be considered correct.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of pre-placed TNT points.
For each $ i \in \{1, \dots, N\} $, let $ p_i = (x_i, y_i, z_i) \in \mathbb{R}^3 $ be the position of the $ i $-th TNT, and $ v_i \in \mathbb{R}^+ $ its volatility constant.
Let $ q = (x, y, z) \in \mathbb{R}^3 $ be the position of Dan’s TNT, and $ V \in \mathbb{R}^+ $ its volatility.
**Constraints**
To trigger all $ N $ TNT pieces simultaneously, Dan’s TNT must satisfy:
$$
V \geq v_i \cdot \| q - p_i \| \quad \text{for all } i \in \{1, \dots, N\}
$$
**Objective**
Minimize $ V $ over all $ q \in \mathbb{R}^3 $:
$$
\min_{q \in \mathbb{R}^3} \max_{1 \leq i \leq N} \left( v_i \cdot \| q - p_i \| \right)
$$