Problem: In 20XX AD, a school competition was held. The tournament has finally left only the final competition. You are one of the athletes in the competition.

The competition you participate in is to compete for the time it takes to destroy all the blue objects placed in the space. Athletes are allowed to bring in competition guns. In the space, there are multiple blue objects, the same number of red objects, and multiple obstacles. There is a one-to-one correspondence between the blue object and the red object, and the blue object must be destroyed by shooting a bullet at the blue object from the coordinates where the red object is placed. The obstacles placed in the space are spherical and the composition is slightly different, but if it is a normal bullet, the bullet will stop there when it touches the obstacle.

The bullet used in the competition is a special bullet called Magic Bullet. This bullet can store magical power, and when the bullet touches an obstacle, it automatically consumes the magical power, and the magic that the bullet penetrates is activated. Due to the difference in the composition of obstacles, the amount of magic required to penetrate and the amount of magic power consumed to activate it are different. Therefore, even after the magic for one obstacle is activated, it is necessary to activate another magic in order to penetrate another obstacle. Also, if the bullet touches multiple obstacles at the same time, magic will be activated at the same time. The amount of magical power contained in the bullet decreases with each magic activation.

While the position and size of obstacles and the amount of magical power required to activate the penetrating magic have already been disclosed, the positions of the red and blue objects have not been disclosed. However, the position of the object could be predicted to some extent from the information of the same competition in the past. You want to save as much magical power as you can, because putting magical power into a bullet is very exhausting. Therefore, assuming the position of the red object and the corresponding blue object, the minimum amount of magical power required to be loaded in the bullet at that time, that is, the magical power remaining in the bullet when reaching the blue object is 0. Let's find the amount of magical power that becomes.

Constraints

* 0 ≤ N ≤ 50
* 1 ≤ Q ≤ 50
* -500 ≤ xi, yi, zi ≤ 500
* 1 ≤ ri ≤ 1,000
* 1 ≤ li ≤ 1016
* -500 ≤ sxj, syj, szj ≤ 500
* -500 ≤ dxj, dyj, dzj ≤ 500
* Obstacles are never stuck in other obstacles
* The coordinates of the object are not inside or on the surface of the obstacle
* Under each assumption, the coordinates of the red object and the blue object do not match.

Input

All inputs are integers. Each number is separated by a single space.


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 is the number of obstacles, and Q is the number of coordinates of the assumed blue and red objects.
* xi, yi, and zi are the x-coordinate, y-coordinate, and z-coordinate that represent the position of the center of the i-th obstacle, respectively.
* ri is the radius of the i-th obstacle.
* li is the amount of magical power consumed by magic to penetrate the i-th obstacle.
* sxj, syj, and szj are the x-coordinate, y-coordinate, and z-coordinate that represent the position of the red object in the jth assumption, respectively.
* dxj, dyj, and dzj are the x-coordinate, y-coordinate, and z-coordinate that represent the position of the blue object in the jth assumption, respectively.

Output

Assuming the position of each pair of red objects and the corresponding blue objects, the amount of magical power to be loaded in the bullet is output on one line, assuming that there are only obstacles, red objects, and one pair of blue objects in space. Let's do it. The bullet is supposed to fly in a straight line from the position of the red object to the position of the blue object, and since the size of the bullet is very small, it is treated as a point.

Examples

Input

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

110


Input

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


Output

9


Input

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

0
2
1
3
0

Solution (in CPP):

Solution:
// Header {{{
// includes {{{
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <sys/time.h>
#include <unistd.h>
#include <vector>
// }}}
using namespace std;
// consts {{{
static const int INF = 1e9;
static const double PI = acos(-1.0);
static const double EPS = 1e-9;
// }}}
// typedefs {{{
typedef long long int LL;
typedef unsigned long long int ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<ULL> VULL;
typedef vector<VULL> VVULL;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef pair<int, int> PII;
typedef complex<int> P;
#define PQ(type) priority_queue<type>
// priority queue reverse
#define PQR(type) priority_queue< type, vector<type>, greater<type> >
// }}}
// macros & inline functions {{{
// syntax sugars {{{
#define FOR(i, b, e) for (typeof(e) i = (b); i < (e); ++i)
#define FORI(i, b, e) for (typeof(e) i = (b); i <= (e); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPI(i, n) FORI(i, 0, n)
#define OPOVER(_op, _type) inline bool operator _op (const _type &t) const
#define ASSIGN_MAX(var, val) ((var) = max((var), (val)))
#define ASSIGN_MIN(var, val) ((var) = min((var), (val)))
// }}}
// conversion {{{
inline int toInt(string s) { int v; istringstream sin(s); sin>>v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout<<x; return sout.str(); }
// }}}
// array and STL {{{
#define ARRSIZE(a) ( sizeof(a) / sizeof(a[0]) )
#define ZERO(a, v) ( assert(v == 0 || v == -1), memset(a, v, sizeof(a)) )
#define F first
#define S second
#define MP(a, b) make_pair(a, b)
#define SIZE(a) ((LL)a.size())
#define PB(e) push_back(e)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define REACH(c, it) for(typeof((c).rbegin()) it=(c).rbegin(); it!=(c).rend(); ++it)
#define EXIST(s, e) ((s).find(e) != (s).end())
// }}}
// bit manipulation {{{
// singed integers are not for bitwise operations, specifically arithmetic shifts ('>>', and maybe not good for '<<' too)
#define IS_UNSIGNED(n) (!numeric_limits<typeof(n)>::is_signed)
#define BIT(n) (assert(IS_UNSIGNED(n)), assert(n < 64), (1ULL << (n)))
#define BITOF(n, m) (assert(IS_UNSIGNED(n)), assert(m < 64), ((ULL)(n) >> (m) & 1))
inline int BITS_COUNT(ULL b) { int c = 0; while(b != 0) { c += (b & 1); b >>= 1; } return c; }
inline int MSB(ULL b) { int c = 0; while(b != 0) { ++c; b >>= 1; } return c-1; }
inline int MAKE_MASK(ULL upper, ULL lower) { assert(lower < 64 && upper < 64 && lower <= upper); return (BIT(upper) - 1) ^ (BIT(lower) - 1); }
// }}}
// for readable code {{{
#define EVEN(n) (n % 2 == 0)
#define ODD(n) (!EVEN(n))
// }}}
// debug {{{
#define arrsz(a) ( sizeof(a) / sizeof(a[0]) )
#define dprt(fmt, ...) if (opt_debug) { fprintf(stderr, fmt, ##__VA_ARGS__); }
#define darr(a) if (opt_debug) { copy( (a), (a) + arrsz(a), ostream_iterator<int>(cerr, " ") ); cerr << endl; }
#define darr_range(a, f, t) if (opt_debug) { copy( (a) + (f), (a) + (t), ostream_iterator<int>(cerr, " ") ); cerr << endl; }
#define dvec(v) if (opt_debug) { copy( ALL(v), ostream_iterator<int>(cerr, " ") ); cerr << endl; }
#define darr2(a) if (opt_debug) { FOR(__i, 0, (arrsz(a))){ darr( (a)[__i] ); } }
#define WAIT() if (opt_debug) { string _wait_; cerr << "(hit return to continue)" << endl; getline(cin, _wait_); }
#define dump(x) if (opt_debug) { cerr << " [L" << __LINE__ << "] " << #x << " = " << (x) << endl; }
// dump vector elements in [s, e)
#define dumpv(v, s, e) if (opt_debug) { cerr << " [L" << __LINE__ << "] " << #v << " = "; FOR(__i, s, e) { cerr << v[__i] << "\t"; } cerr << endl; }
#define dumpl(x) if (opt_debug) { cerr << " [L" << __LINE__ << "] " << #x << endl << (x) << endl; }
#define dumpf() if (opt_debug) { cerr << __PRETTY_FUNCTION__ << endl; }
#define where() if (opt_debug) { cerr << __FILE__ << ": " << __PRETTY_FUNCTION__ << " [L: " << __LINE__ << "]" << endl; }
#define show_bits(b, s) if(opt_debug) { REP(i, s) { cerr << BITOF(b, s-1-i); if(i%4 == 3) cerr << ' '; } cerr << endl; }

// ostreams {{{
// complex
template<typename T> ostream& operator<<(ostream& s, const complex<T>& d) {return s << "(" << d.real() << ", " << d.imag() << ")";}

// pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& d) {return s << "(" << d.first << ", " << d.second << ")";}

// vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d) {
	int len = d.size();
	REP (i, len) {
		s << d[i]; if (i < len - 1) s << "\t";
	}
	return s;
}

// 2 dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& d) {
	int len = d.size();
	REP (i, len) {
		s << d[i] << endl;
	}
	return s;
}

// map
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr) {
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}
// }}}
// }}}
// }}}
// time {{{
inline double now(){ struct timeval tv; gettimeofday(&tv, NULL); return (static_cast<double>(tv.tv_sec) + static_cast<double>(tv.tv_usec) * 1e-6); }
// }}}
// string manipulation {{{
inline VS split(string s, char delimiter) { VS v; string t; REP(i, s.length()) { if(s[i] == delimiter) v.PB(t), t = ""; else t += s[i]; } v.PB(t); return v; }
inline string join(VS s, string j) { string t; REP(i, s.size()) { t += s[i] + j; } return t; }
// }}}
// geometry {{{
#define Y real()
#define X imag()
// }}}
// 2 dimentional array {{{
enum { UP, RIGHT, DOWN, LEFT, UP_RIGHT, DOWN_RIGHT, DOWN_LEFT, UP_LEFT };
P dydx4[4] = { P(-1, 0), P(0, 1), P(1, 0), P(0, -1) };
P dydx8[8] = { P(-1, 0), P(0, 1), P(1, 0), P(0, -1), P(-1, 1), P(1, 1), P(1, -1), P(-1, -1) };
bool in_field(int H, int W, P p) {
	return (0 <= p.Y && p.Y < H) && (0 <= p.X && p.X < W);
}
// }}}
// input and output {{{
inline void input(string filename) {
	freopen(filename.c_str(), "r", stdin);
}
inline void output(string filename) {
	freopen(filename.c_str(), "w", stdout);
}
// }}}
// }}}

// Header under development {{{

int LCM(int a, int b) {
	// FIXME
	return a * b;
}

// Fraction class {{{
// ref: http://martin-thoma.com/fractions-in-cpp/
class Fraction {
	public:
		ULL numerator;
		ULL denominator;
		Fraction(ULL _numerator, ULL _denominator) {
			assert(_denominator > 0);
			numerator = _numerator;
			denominator = _denominator;
		};

		Fraction operator*(const ULL rhs) {
			return Fraction(this->numerator * rhs, this->denominator);
		};

		Fraction operator*(const Fraction& rhs) {
			return Fraction(this->numerator * rhs.numerator, this->denominator * rhs.denominator);
		}

		Fraction operator+(const Fraction& rhs) {
			ULL lcm = LCM(this->denominator, rhs.denominator);
			ULL numer_lhs = this->numerator * (this->denominator / lcm);
			ULL numer_rhs = rhs.numerator * (rhs.numerator / lcm);
			return Fraction(numer_lhs + numer_rhs, lcm);
		}

		Fraction& operator+=(const Fraction& rhs) {
			Fraction result = (*this) + rhs;
			this->numerator = result.numerator;
			this->denominator = result.denominator;
			return *this;
		}
};

std::ostream& operator<<(std::ostream &s, const Fraction &a) {
	if (a.denominator == 1) {
		s << a.numerator;
	} else {
		s << a.numerator << "/" << a.denominator;
	}
	return s;
}

// }}}

// }}}

bool opt_debug = false;

// Geometry <3 {{{
class GeometryUtil {
	public:
		bool eql(double a, double b) { return abs(a - b) < EPS; }
		bool lt(double a, double b) { return b - a >= EPS; }
		bool lte(double a, double b) { return lt(a, b) || eql(a, b); }
		bool gt(double a, double b) { return !lte(a, b); }
		bool gte(double a, double b) { return !lt(a, b); }
		bool eql(P a, P b) { return eql(a.Y, b.Y) && eql(a.X, b.X); }
		GeometryUtil() {
		}
};

GeometryUtil geo = GeometryUtil();

template<typename T>
class Vector3D {
	public:
		T x, y, z;
		Vector3D(T _x, T _y, T _z): x(_x), y(_y), z(_z) {
		}

		T abs() {
			return sqrt(pow(x, 2) + pow(y, 2) + pow(z, 2));
		}

		T dot(Vector3D<T> rhs) {
			return x * rhs.x + y * rhs.y + z * rhs.z;
		}

		Vector3D<T> cross(Vector3D<T> rhs) {
			return Vector3D(y*rhs.z - z*rhs.y, z*rhs.x - x*rhs.z, x*rhs.y - y*rhs.x);
		}

		// check if this Vector3D (as a point) is on a line (a-b)
		const bool is_upon(const Vector3D<T> a, const Vector3D<T> b) const {
			dump((b-a).cross(b-(*this)).abs());
			dump(geo.eql((b-a).cross(b-(*this)).abs(), 0));
			dump((b-a).dot((*this)-a));
			dump(geo.gt( (b-a).dot((*this)-a), 0 ));
			dump((a-b).dot((*this)-b));
			dump(geo.gt( (a-b).dot((*this)-b), 0 ));

			return geo.eql( (b-a).cross(b-(*this)).abs(), 0 ) &&
				geo.gt( (b-a).dot((*this)-a), 0 ) &&
				geo.gt( (a-b).dot((*this)-b), 0 );
		}

		// Add vector
		Vector3D<T> operator+(const Vector3D<T>& rhs) const {
			return Vector3D<T>(x + rhs.x, y + rhs.y, z + rhs.z);
		}

		// Subtract vecrtor
		Vector3D<T> operator-(const Vector3D<T>& rhs) const {
			return Vector3D<T>(x - rhs.x, y - rhs.y, z - rhs.z);
		}

		// Multiply by scala value
		template<typename Scala>
		Vector3D<T> operator*(const Scala rhs) const {
			return Vector3D<T>(x * rhs, y * rhs, z * rhs);
		}
};
template<typename T>
ostream& operator<<(ostream& out, const Vector3D<T>& v) {
	return out << "(" << v.x << ", " << v.y << ", " << v.z << ")";
}

class Sphere {
	int x, y, z, r;
	public:
		Sphere(int _x, int _y, int _z, int _r) : x(_x), y(_y), z(_z), r(_r) {
		}
};

// }}}

class Obstacle {
	public:
		int x, y, z, r;
		ULL magic;
		Obstacle(int _x, int _y, int _z, int _r, ULL _magic) : x(_x), y(_y), z(_z), r(_r), magic(_magic) {
		}
};
ostream& operator<<(ostream& out, const Obstacle& o) {
	return out << "((" << o.x << ", " << o.y << ", " << o.z << "), " << o.r << ", " << o.magic << ")";
}


int main(int argc, char** argv) {
	std::ios_base::sync_with_stdio(false);
	// set options {{{
	int __c;
	while ( (__c = getopt(argc, argv, "d")) != -1 ) {
		switch (__c) {
			case 'd':
				opt_debug = true;
				break;
			default:
				abort();
		}
	}
	// }}}

	// opt_debug = true;
	// input("./inputs/3.txt");
	// output("./outputs/0.txt");

	int N, Q; cin >> N >> Q;
	vector<Obstacle> obstacles;
	REP (i, N) {
		int x, y, z, r; ULL l; cin >> x >> y >> z >> r >> l;
		obstacles.PB(Obstacle(x, y, z, r, l));
	}

	REP (t, Q) {
		int x, y, z; cin >> x >> y >> z;
		Vector3D<double> red(x, y, z);
		cin >> x >> y >> z;
		Vector3D<double> blue(x, y, z);
		ULL ans = 0;
		REP (i, N) {
			Obstacle o = obstacles[i];
			dump(red);
			dump(blue);
			dump(o);
			// Move vectors so that the center of the obstacle become the origin
			Vector3D<double> s = red - Vector3D<double>(o.x, o.y, o.z);
			Vector3D<double> e = blue - Vector3D<double>(o.x, o.y, o.z);
			Vector3D<double> v = e - s;
			o.x = o.y = o.z = 0;
			dump(s);
			dump(e);
			dump(v);
			dump(o);

			dump(s.dot(v));
			dump(v.abs());
			double x = - s.dot(v) / (v.abs() * v.abs());
			dump(x);
			dump(v * x);
			Vector3D<double> nearest = s + v * x;
			dump(nearest);
			dump(nearest.abs());
			dump(nearest.is_upon(s, e));
			if (nearest.abs() <= o.r + EPS && nearest.is_upon(s, e)) {
				dump(o.magic);
				ans += o.magic;
				dump(ans);
			}
		}
		dump(ans);
		cout << ans << endl;
	}

	return 0;
}

// vim: foldmethod=marker