[Lydsy2017年4月月赛]量子破碎

时间限制:4s      空间限制:128MB

题目描述

 这里省略对游戏情节的剧透,有兴趣可以去Steam上搜索Quantum Break。你被请来帮助小Q同学决策一个游戏场景

的操作。假设主角位于三维空间的原点,有 n 个敌人向他射击,其中第 i 个敌人可以对主角产生 a_i 点伤害。
此外,空间中还有 m 个装有时元粒子的桶,其中引爆第 i 个桶可以使以第 i 个桶为中心,半径为 r_i 的球型区
域内部的时间静止一段时间,这也意味着子弹在球型区域内无法运动(不包括子弹轨迹与区域相切的情况)。主角
需要利用时光机器回到过去去拯救他的兄弟,现在时光机器正在原点启动,而他要在原地保护时光机器的启动过程
,这意味着他只能在原地使用时间能力来防御攻击。小Q可以操纵主角在这个场景使用两种时间能力,时间引爆和
时间护盾。一次时间引爆可以引爆一个桶,引爆不受到时间静止的影响,这意味着主角可以成功引爆一个已经在时
间静止区域内的桶。而时间护盾则是在以使用者本身为中心的一定区域内产生时间静止,从而抵御子弹的伤害。给
出每个敌人和桶的信息,假设杰克已经引爆所有的桶,但是其中 k (0≤k≤m) 个桶的时间静止效果即将消失,你
需要计算杰克在这种情况下要用时间护盾抵御的伤害之和的最大值 s(k) 。为了简化问题,你只需要输出sigma((i
+1)*s(i)),0<=i<=m,其对2^64取模的值而不是每个 s(k) 。时间是一种强大的力量,它也是头号杀手。注意时间限
制与空间限制。


输入格式

 第一行包含一个正整数 T ,表示有 T 组数据,满足 T≤200 。

接下来是测试数据。对于每组测试数据:
第一行包含两个正整数 n 和 m ,满足 1≤n≤15,1≤m≤10^5 。
接下来 n 行给出敌人的信息,其中第 i 行包含四个整数 x_i,y_i,z_i,a_i ,表示第 i 个敌人的坐标是 (x_i,y_i,z_i)
其能对主角造成的伤害是 a_i ,满足 0≤|x_i |,|y_i |,|z_i |≤10^4,1≤a_i≤10^4 。
接下来 m 行给出桶的信息,其中第 i 行包含四个整数 x_i,y_i,z_i,r_i ,表示第 i 个桶的坐标是 (x_i,y_i,z_i) 
其爆炸的半径是 r_i ,满足 0≤|x_i |,|y_i |,|z_i |≤10^4,1≤r_i≤10^4 。
保证所有给出的点(包括主角的位置)互不相同。
不超过 10 组数据满足 m≥100 ,不超过 2 组数据满足 m≥10^4 。


输出格式

对于每组测试数据,输出一行一个非负整数,表示这组数据的答案。


样例输入

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

样例输出

105

提示

没有写明提示


题目来源

鸣谢Tangjz提供试题