# Vines ###### tags: `cp` > Zanite Ryu is an adventurer-turned-treasure hunter. One day, he heard about the myth of Strofe, a magical forest with majestic treasures. The treasure(s) in Strofe - gold bars - are located on the top of one or more trees in the forest. There are $T$ trees in Strofe, numbered from $1$ to $T$. The $i^\text{th}$ tree is located at $(x_i, y_i)$ and has $g_i$ gold bars on top of it. (If it has no gold on top of it, then $g_i = 0$.) Ryu, without hesitating, makes his way to Strofe with a helicopter. Here's the catch: the forest has deadly mythical creatures watching over it. They can't attack Ryu if one of these conditions hold: - Ryu can look in such a way that there is no tree visible in his $180^\circ$ field of vision, not including the tree(s) located exactly to the left or right. - Ryu is touching a tree. (This includes standing on top of a tree and swinging using a tree's vine.) Luckily, there are $V$ two-way vines that Ryu can use to navigate between trees without needing to step on the ground. These vines are numbered from $1$ to $V$, and the $i^\text{th}$ vine connects trees number $u_i$ and $v_i$. Ryu wants to know the maximum number of gold bars he can get from one trip if he needs to start and end at the same point. **Said point must be safe.** Ryu also wants to know the minimum distance he needs to walk on the ground in that trip. ## Input Format <pre> T x<sub>1</sub> y<sub>1</sub> g<sub>1</sub> x<sub>2</sub> y<sub>2</sub> g<sub>2</sub> x<sub>3</sub> y<sub>3</sub> g<sub>3</sub> ⋮ x<sub>T</sub> y<sub>T</sub> g<sub>T</sub> V u<sub>1</sub> y<sub>1</sub> u<sub>2</sub> y<sub>2</sub> u<sub>3</sub> y<sub>3</sub> ⋮ u<sub>V</sub> y<sub>V</sub> </pre> ## Output Format Output two integers, separated by a space, in a single line: the maximum number of gold bars Ryu can get and the minimum distance Ryu needs to walk on the ground to get that many gold bars. Your answer is considered correct if its difference with the judge's answer is less than $10^{-6}$. ## Constraints - $1 \leq T \leq 10^6$ - $0 \leq x_i, y_i, g_i \leq 10^9$ for $1 \leq i \leq T$ - $0 \leq V \leq \min \left(10^6, \frac{1}{2}T(T-1) \right)$ - $1 \leq u_i, v_i \leq T$ for $1 \leq i \leq V$ - $u_i \neq v_i$ for $1 \leq i \leq V$