一个温暖晴朗的日子,国王科帕决定参观位于中央公园的射击场,并尝试赢得大奖——粉色大毛绒熊猫。国王不擅长射击,所以他邀请你来帮助他。
射击场是一个无限大的垂直平面,其上有笛卡尔坐标系。目标是该平面上的点。每个目标由它的坐标 xi 和 yi、出现时间 ti 和数字 pi 来描述,这给出了 Copa 在瞄准该目标时击中该目标的概率。
目标瞬间出现并立即消失,因此 Copa 只有在此时瞄准 (xi, yi) 时才能击中目标。飞机上瞄准镜的移动速度等于1。Copa事先知道目标的所有信息(记住,他是国王!)。他希望以最佳方式进行比赛,从而最大化命中目标数量的预期值。他此刻可以瞄准任何目标0。
输入
第一行包含整数 n (1 ≤ n ≤ 1000) — 射击场中的目标数量。接下来是 n 行,每行描述一个目标。每个描述由四个数字 xi、yi、ti、pi 组成(其中 xi、yi、ti — 整数,- 1000 ≤ xi、yi ≤ 1000、0 ≤ ti ≤ 109,实数 pi 给出小数点后不超过 6 位数字,0 ≤ pi ≤ 1)。任何两个目标都不能位于同一点。
输出
输出国王射中目标数量的最大期望值。如果您的答案与正确答案的差异不超过 10 - 6,则您的答案将被接受。
示例
输入 #1
1 0 0 0 0.5
输出 #1
0.5000000000
输入 #2
2 0 0 0 0.6 5 0 5 0.7
输出 #2
1.3000000000