Kanna is interested in catching insects. She was used to catching insects with her sweep net. But
resently, she found it was more effective to set traps. She plans to set N circular traps, k th trap
is at (X k ,Y k ) and its radius is R k . It can capture W k insects. When two traps are intersectant
(excluding tangent) they will become useless. So Kanna wants to choose some traps to set so that
she can catch maximum insects. Can you help her?
One integer N(1 ≤ N ≤ 2000) in the first line.
In the following N lines, k-th line has 4 integers X k ,Y k ,R k ,W k (1 ≤ X k ,Y k ,R k ≤ 10 8 ,1 ≤ Wk ≤ 10 6 ).
All these input have been explained above.
Because the area she set traps is so narrow, each horizontal line will cross (excluding tangent) at
most two traps from the N traps.
One integer in one line, represents the maximum insects Kanna can catch.
6
1 1 1 1
3 1 1 2
1 4 2 3
4 8 3 4
4 3 1 5
2 10 3 3
15