#1323. plane平面

内存限制:162 MiB 时间限制:5 Sec

题目描述

空间中有N个点,其中第i个点的坐标是(xi, yi, zi).此外我们为每一个点分配一个权值,第i个点的权是ci. 任何一个过原点(0, 0, 0)的平面,将所有点分成两个部分(正好在平面上的点可以任意选择被放入哪一个部分),选择其中点的权值之和较大的一个部分作为平面的权值.请你找到这样一个平面,其权值最大.

输入格式

第一行有一个整数N,表示空间中点的个数. 以下N行,每行4个整数,xi, yi, zi和ci,描述第i个点的坐标和权值.

输出格式

输出文件中只包含一个整数,表示所有过原点的平面中最大的权值.

样例

样例输入


			
6
1 0 0 -4
-1 0 0 2
0 1 0 3
0 -1 0 -5
0 0 1 5
0 0 -1 -5

样例输出


			
10

数据范围与提示

30%的数据中,1 <= N <= 50 100%的数据中,1 <= N <= 1 000 100%的数据中, |xi|, |yi|, |zi|, |ci| <= 10 000