Melody is preparing a cake for a very special occasion. She's starting off with a square cake, though she'd like it cut down into a more unique shape. When viewed from above, it can be represented as a square on a 2D plane, with opposite corners at coordinates \((0, 0)\) and \((S, S)\).

Out of countless contenders, Melody has interviewed \(N\) certified cake-cutting consultants, asking how the cake should be cut down. The \(i\)th consultant, who has a competence value of \(C_i\), has proposed that two cuts should be performed: the first being a line segment between coordinates \((X_{i,1}, Y_{i,1})\) and \((X_{i,2}, Y_{i,2})\), and the second between \((X_{i,3}, Y_{i,3})\) and \((X_{i,4}, Y_{i,4})\). Each of these four points is exactly on a side of the cake (but not on a corner), the two points describing each line segment are not on the same side of the cake, and the two line segments do not share any points in common (in other words, they don't intersect nor have any equal endpoints). Therefore, the two cuts would split the cake into three non-empty polygonal sections. Of those, the middle section (the one between the two cuts) would become their **proposed cake shape**, with the other two sections discarded.

For example, the following diagram illustrates a cake with \(S = 10\) and a consultant's pair of proposed cuts (from \((4, 10)\) to \((2, 0)\) and from \((0, 9)\) to \((2, 10)\)), with their resulting proposed cake shape highlighted in blue:

{{PHOTO_ID:186542789854750}}

Melody wants to hire one or more of the consultants to form a committee, whose members will then deliberate on the final shape of the cake. That is, she calls for a completely competent consulting committee capable of coming to a consensus on a commendable cake-cutting configuration. Clearly.

She wants the sum of the hired consultants' competence values to be as large as possible, no matter how many of them she has to hire. However, she won't allow a pair of consultants to both be part of the committee if their cake-cutting proposals *fundamentally differ*, which is the case if their proposed cake shapes do not share any points in common (in other words, if those two polygons are entirely disjoint, including at their edges and vertices).

For example, the following diagram additionally includes another consultant's pair of proposed cuts (from (7, 10) to (10, 7) and from (10, 5) to (5, 10)), with their proposed cake shape highlighted in red. Since these two proposed cake shapes do not overlap at all, the two proposals fundamentally differ, meaning that if one of these consultants is hired, the other cannot also be hired:

{{PHOTO_ID:3047534892140325}}

On the other hand, each of the following cakes features a pair of proposals which do not fundamentally differ, due to the proposed cake shapes sharing at least one point in common (meaning that, for each cake, the two consultants could be hired together):

{{PHOTO_ID:139722534273576}}

Help Melody determine the maximum combined competence of consultants who can form the committee, such that no two of them have fundamentally differing cake-cutting proposals.

# Constraints

\(1 \le T \le 80\)
\(1 \le N \le 800\)
\(2 \le S \le 100,000,000\)
\(1 \le C_i \le 500,000\)
\(0 \le X_{i,j}, Y_{i,j} \le S\)

The sum of \(N\) across all special occasions is at most 20,000.

# Input

Input begins with an integer \(T\), the number of special occasions. For each occasion, there are \(N + 1\) lines. The first line contains 2 space-separated integers, \(S\) and \(N\). \(N\) lines follow, the \(i\)th of which contains the 9 space-separated integers \(C_i\), \(X_{i,1}\), \(Y_{i,1}\), \(X_{i,2}\), \(Y_{i,2}\), \(X_{i,3}\), \(Y_{i,3}\), and \(X_{i,4}\), \(Y_{i,4}\).

# Output

For the \(i\)th special occasion, print a line containing *"Case #i: "*, followed by a single integer, the maximum combined competence of cake-cutting consultants who can form the committee.

# Explanation of Sample

The first cake (along with the consultants' proposed cake shapes) looks as follows:

{{PHOTO_ID:2722961511304050}}

The 1st and 2nd consultants can't both be hired together, but either can be hired alongside the 3rd consultant. So, the best Melody can do is to hire the 2nd and 3rd consultants for a combined competence of \(30 + 40 = 70\).

The second cake looks as follows:

{{PHOTO_ID:408936830244710}}

Melody can hire all three consultants.

The third cake looks as follows:

{{PHOTO_ID:386528679257402}}

The fourth cake looks as follows:

{{PHOTO_ID:863939674419710}}

The fifth cake looks as follows:

{{PHOTO_ID:424906348725741}}