#ifdef LOCAL #define _GLIBCXX_DEBUG #endif // LOCAL #pragma GCC optimize("O3") #include using namespace std; using ll = long long; void solve_test (istream &cin, ostream &cout) { int d; cin >> d; vector> x(3); vector len(3); for (int i = 0; i < 3; i++) { int n; cin >> n >> len[i]; assert(1 <= len[i] && len[i] <= d); x[i].resize(n); for (auto &it : x[i]) cin >> it; sort(x[i].begin(), x[i].end()); } const int big = int(1e8); for (int i = 0; i < 3; i++) { x[i].insert(x[i].begin(), -big); if (i == 1) x[i].push_back(+big); assert(is_sorted(x[i].begin(), x[i].end())); } vector n(3); for (int i = 0; i < 3; i++) n[i] = int(x[i].size()); const ll inf = ll(1e18); vector>> dp(n[0], vector>(n[1], vector(n[2], -inf))); dp[0][0][0] = 0; auto get_ban = [&] (const int side, const int i) { const int lshift = d - 2 * len[1]; int rshift = 2 * len[side] - d; if (rshift <= lshift) rshift = lshift + 1; return pair(x[1][i] + lshift, x[1][i] + rshift); }; for (int side = 0; side <= 2; side += 2) { auto ban_sma = get_ban(side, 0); auto ban_big = get_ban(side, n[1] - 1); assert(ban_sma.second < x[side][1]); assert(x[side][n[side] - 2] < ban_big.first); } ll ans = -inf; vector i(3), j(3); for (i[0] = 0; i[0] < n[0]; i[0]++) for (i[1] = 0; i[1] < n[1]; i[1]++) for (i[2] = 0; i[2] < n[2]; i[2]++) { ans = max(ans, dp[i[0]][i[1]][i[2]]); { j = i; for (j[1] = j[1] + 1; j[1] < n[1]; j[1]++) if (x[1][j[1]] - x[1][i[1]] >= len[1]) { ll cur = dp[i[0]][i[1]][i[2]] + ll(len[1]) * len[1]; j[0] = i[0], j[2] = i[2]; for (int side = 0; side <= 2; side += 2) { auto ban_i = get_ban(side, i[1]); auto ban_j = get_ban(side, j[1]); assert(ban_i.first <= ban_j.first && ban_i.second <= ban_j.second); if (ban_i.second <= ban_j.first) { int lseg = ban_i.second, rseg = ban_j.first; int cnt = 0, last = x[side][i[side]]; for (int t = 0; t < n[side]; t++) if (lseg <= x[side][t] && x[side][t] <= rseg) if (x[side][t] >= last + len[side]) { last = x[side][t]; j[side] = t; cnt++; } cur += ll(cnt) * ll(len[side]) * ll(len[side]); } } // cerr << j[0] << ' ' << j[1] << ' ' << j[2] << ' ' << cur << endl; dp[j[0]][j[1]][j[2]] = max(dp[j[0]][j[1]][j[2]], cur); } } } ans -= ll(len[1]) * ll(len[1]); assert(ans > 0); cout << ans << endl; } struct point { ll x, y; point() : x(0), y(0) {} point (const ll x_, const ll y_) : x(x_), y(y_) {} point operator + (const point &o) const { return point(x + o.x, y + o.y); } point operator - (const point &o) const { return point(x - o.x, y - o.y); } ll operator * (const point &o) const { return ll(x) * o.x + ll(y) * o.y; } ll operator % (const point &o) const { return ll(x) * o.y - ll(o.x) * y; } bool operator < (const point &o) const { return x < o.x || (x == o.x && y < o.y); } bool operator == (const point &o) const { return x == o.x && y == o.y; } }; struct triag { int x, y, len; vector get() const { return vector{point(2 * x, 2 * y), point(2 * (x - len), 2 * (y - len)), point(2 * (x + len), 2 * (y - len))}; } }; tuple line (const point &l, const point &r) { ll a = (r.y - l.y), b = (l.x - r.x); ll c = -(ll(a) * l.x + ll(b) * l.y); ll g = __gcd(__gcd(abs(a), abs(b)), abs(c)); a /= g, b /= g, c /= g; return tuple(a, b, c); } bool intersect (const triag &l, const triag &r) { auto lt = l.get(); auto rt = r.get(); vector p; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { ll a1, b1; ll c1; ll a2, b2; ll c2; tie(a1, b1, c1) = line(lt[i], lt[i + 1 == 3 ? 0 : i + 1]); tie(a2, b2, c2) = line(rt[j], rt[j + 1 == 3 ? 0 : j + 1]); const ll det = a1 * b2 - a2 * b1; if (det != 0) { assert(abs(det) <= 2); assert((b1 * c2 - b2 * c1) % det == 0); assert((a1 * c2 - a2 * c1) % det == 0); p.push_back(point(+(b1 * c2 - b2 * c1) / det, -(a1 * c2 - a2 * c1) / det)); } } for (auto it : lt) p.push_back(it); for (auto it : rt) p.push_back(it); sort(p.begin(), p.end()); p.resize(unique(p.begin(), p.end()) - p.begin()); vector take(p.size(), 1); for (int j = 0; j < int(p.size()); j++) for (int i = 0; i < 3; i++) { ll a, b, c; point cur = lt[i], nxt = lt[i + 1 == 3 ? 0 : i + 1]; if ((nxt - cur) % (p[j] - cur) < 0) take[j] = 0; cur = rt[i], nxt = rt[i + 1 == 3 ? 0 : i + 1]; if ((nxt - cur) % (p[j] - cur) < 0) take[j] = 0; } if (count(take.begin(), take.end(), 1) > 1) return true; return false; } void brut_test (istream &cin, ostream &cout) { // triag t1{100, 9, 20}; // triag t2{50, 0, 40}; // triag t3{50, 40, 40}; // cerr << intersect(t1, t2) << endl; // cerr << intersect(t1, t3) << endl; // cerr << intersect(t2, t3) << endl; // cerr << intersect(t2, t1) << endl; // cerr << intersect(t3, t1) << endl; // cerr << intersect(t3, t2) << endl; // cerr << "adfas" << endl; int d; cin >> d; vector len(3); vector triags; for (int i = 0; i < 3; i++) { int n; cin >> n >> len[i]; assert(1 <= len[i] && len[i] <= d); for (int j = 0; j < n; j++) { int y; cin >> y; // cerr << d * i << ' ' << y << ' ' << len[i] << endl; triags.push_back(triag{d * i, y, len[i]}); } } const int cnt = int(triags.size()); ll ans = 0; cerr << "triag data!" << endl; for (int i = 0; i < cnt; i++) cerr << triags[i].x << ' ' << triags[i].y << ' ' << triags[i].len << endl; cerr << "intersect data!" << endl; for (int i = 0; i < cnt; i++) for (int j = i + 1; j < cnt; j++) if (intersect(triags[i], triags[j])) cerr << i << ' ' << j << endl; cerr << "end!" << endl; for (int mask = 0; mask < (1 << cnt); mask++) { ll cur = 0; for (int i = 0; i < cnt; i++) if ((mask >> i) & 1) cur += ll(triags[i].len) * ll(triags[i].len); bool ok = true; for (int i = 0; ok && i < cnt; i++) if ((mask >> i) & 1) for (int j = i + 1; ok && j < cnt; j++) if ((mask >> j) & 1) if (intersect(triags[i], triags[j])) ok = false; if (ok) ans = max(ans, cur); } cout << ans << endl; } void solve (istream &cin, ostream &cout) { int t; cin >> t; for (int i = 0; i < t; i++) brut_test(cin, cout); } void gen (ostream &cout) { static mt19937 rng; const int d = rng() % 10 + 1; cout << d << endl; for (int i = 0; i < 3; i++) { const int n = rng() % 3 + 1; const int len = rng() % d + 1; cout << n << " " << len << endl; for (int j = 0; j < n; j++) cout << rng() % 20 << ' '; cout << endl; } } int main() { // while (true) // { // stringstream test; // gen(test); // stringstream my_in(test.str()), my_out; // stringstream br_in(test.str()), br_out; // // solve_test(my_in, my_out); // brut_test(br_in, br_out); // cerr << test.str() << endl; // cerr << my_out.str() << ' ' << br_out.str() << endl; // assert(my_out.str() == br_out.str()); // } #ifdef LOCAL ifstream in("input.txt"); ofstream out("output.txt"); solve(in, out); #else brut_test(cin, cout); #endif }