西暦20XX 年，学校対抗魔法競技大会が開かれていた．大会もいよいよ，最終競技を残すのみとなった．あなたはその競技の選手の1 人である．

あなたが出場する競技は，空間内に配置された青いオブジェをすべて破壊するまでの時間を競うというものである．選手は競技用の銃の持込が許可されている．空間内には複数の青いオブジェと同じ数の赤いオブジェ，そして複数の障害物が配置されている．青いオブジェと赤いオブジェは1 対1 に対応しており，赤いオブジェが配置されている座標から青いオブジェに弾を撃つことで青いオブジェを破壊しなければならない．空間内に配置されている障害物は球状であり，少しずつ組成が異なっているが，通常の弾であれば障害物に触れると弾はその場に止まってしまう．

競技に使われる弾はMagic Bullet という特殊な弾である．この弾は魔力をため込むことができ，弾が障害物に接触した際に自動的に魔力を消費し，弾が貫通する魔法が発動する．障害物の組成の違いから，貫通するために必要な魔法やその発動のために消費する魔力の量は異なっている．このため，ある障害物に対する魔法が発動した後であっても，別の障害物を貫通するためには新たに別の魔法を発動する必要がある．また，弾が複数の障害物に同時に接触した場合は同時に魔法が発動する．弾に込められた魔力の量は魔法の発動のたびに減少する．

障害物の位置や大きさ，貫通する魔法の発動に必要な魔力の量はすでに公開されているのに対し，赤いオブジェ，青いオブジェの位置は公開されていない．しかし，過去の同一競技の情報から，ある程度オブジェの位置を予想することができた．魔力を弾にこめることは非常に体力を消耗してしまうため，あなたは魔力をできるだけ節約したいと考えた．そこで，赤いオブジェとそれに対応する青いオブジェの位置を仮定して，そのときに弾にこめるべき必要な魔力の最小量，つまり，青いオブジェに到達している時点で弾に残っている魔力が0 になる魔力の量を求めよう．

Input

入力はすべて整数である．それぞれの数は1 つの空白により区切られる．

N Q
x1 y1 z1 r1 l1
:
xN yN zN rN lN
sx1 sy1 sz1 dx1 dy1 dz1
:
sxQ syQ szQ dxQ dyQ dzQ

• N は障害物の個数であり，Q は仮定した青いオブジェと赤いオブジェの座標の組の個数である．
• x_i, y_i, z_i はそれぞれ i 個目の障害物の中心の位置を表す x 座標，y 座標，z 座標である．
• r_i は i 個目の障害物の半径である．
• l_i は i 個目の障害物を貫通するための魔法で消費する魔力の量である．
• sx_j, sy_j, sz_j はそれぞれ j 番目の仮定における赤いオブジェの位置を表す x 座標，y 座標，z 座標である．
• dx_j, dy_j, dz_j はそれぞれ j 番目の仮定における青いオブジェの位置を表す x 座標，y 座標，z 座標である．

Constraints

• 0 ≤ N ≤ 50
• 1 ≤ Q ≤ 50
• -500 ≤ x_i, y_i, z_i ≤ 500
• 1 ≤ r_i ≤ 1,000
• 1 ≤ l_i ≤ 10¹⁶
• -500 ≤ sx_j, sy_j, sz_j ≤ 500
• -500 ≤ dx_j, dy_j, dz_j ≤ 500
• 障害物が他の障害物にめり込んでいることはない
• オブジェの座標は障害物の内部，表面にはない
• それぞれの仮定において，赤いオブジェと青いオブジェの座標は一致しない

Output

それぞれ1 組の赤いオブジェとそれに対応する青いオブジェの位置の仮定において，空間中に障害物と赤いオブジェと青いオブジェ1 対とのみがあるものとして，弾にこめるべき魔力の量を1 行に出力せよ．弾は赤いオブジェの位置から青いオブジェの位置まで一直線に飛ぶものとし，弾の大きさは非常に小さいので点として扱う．

Sample Input 1

5 1
0 10 0 5 2
0 20 0 5 12
0 30 0 5 22
0 40 0 5 32
0 50 0 5 42
0 0 0 0 60 0

Output for the Sample Input 1

110

Sample Input 2

1 1
10 5 0 5 9
0 0 0 9 12 0

Output for the Sample Input 2

9

Sample Input 3

5 5
-38 -71 -293 75 1
-158 -38 -405 66 1
-236 -303 157 266 1
316 26 411 190 1
207 -312 -27 196 1
-50 292 -375 -401 389 -389
460 278 409 -329 -303 411
215 -220 -200 309 -474 300
261 -494 -87 -300 123 -463
386 378 486 -443 -64 299

Output for the Sample Input 3

0
2
1
3
0