1489: 小D的圆圈游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:15 Solved:2

Description

小D和小M想出了一个无聊的游戏。
首先将一张纸看作一个平面直角坐标系,首先小D会在纸上画n个圆,这n个圆两两不相交也不想切。小D把每个圆的圆心坐标和半径告诉小M,对于每个圆,小D认为都有一个对应的价值wi,现在小D希望小M从中选出一些圆,要求选出的价值和最大。
这个问题当然很简单,体现不出小M的水平,因此小D要求,小M所选出的圆,不允许有一个圆被另一个圆包含的情况。因为圆的分布很复杂,所以小M一时间解决不了这个问题,他只好拜托你来帮他求解。
数据保证:$n<=2 \times 10^5$,$0<x,y,r<= 10^8$, $w_i < 1000 $

Input

输入文件的第一行一个整数n表示圆的数量
接下来n行每行4个整数,xi、yi、ri和wi分别代表圆心坐标、半径和对应价值

Output

输出包括一行,包含一个整数,代表选出的圆的最大价值

Sample Input Copy

3
3 4 2 3
9 4 1 4
6 4 7 5

Sample Output Copy

7

HINT

选择第一个和第三个圆,价值和为7