#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

using ll = long long;
using ld = long double;

struct Point{
	ll x, y;

	Point() {}
	Point(ll _x, ll _y): x(_x), y(_y) {}

	Point operator + (const Point &P) const {
		return Point(x + P.x, y + P.y);
	}

	Point operator - (const Point &P) const {
		return Point(x - P.x, y - P.y);
	}

	Point operator - () const {
		return Point(-x, -y);
	}

	bool operator < (const Point &P) const {
		if (y != P.y) return y < P.y;
		return x < P.x;
	}
};

struct Line{
	ll A, B, C;

	Line() {}
	Line(ll _A, ll _B, ll _C): A(_A), B(_B), C(_C) {}
	Line(Point p1, Point p2){
		A = p1.y - p2.y;
		B = p2.x - p1.x;
		C = -A * p1.x - B * p1.y;
	}
};

ld cross(Point p1, Point p2){
	return p1.x * p2.y - p1.y * p2.x;
}

using Polygon = vector<Point>;

void reorder(Polygon &p){
	int root = 0;
	for (int i = 0; i < p.size(); i++){
		if (p[i] < p[root]) root = i;
	}
	rotate(p.begin(), p.begin() + root, p.end());
}

Polygon mincowski_sum(Polygon A, Polygon B){
	reorder(A); reorder(B);
	A.push_back(A[0]);
	A.push_back(A[1]);
	B.push_back(B[0]);
	B.push_back(B[1]);

	Polygon res;
	int i = 0, j = 0;
	while (i < A.size() - 2 || j < B.size() - 2){
		res.push_back(A[i] + B[j]);
		ld C = cross(A[i+1] - A[i], B[j+1] - B[j]);
		if (C >= 0 && i < A.size() - 2) i++;
		if (C <= 0 && j < B.size() - 2) j++;
	}
	return res;
}

ll orientation(Point A, Point B, Point C){
	ll v = A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
	if (v < 0) return -1;
	if (v > 0) return 1;
	return 0;
}

bool cw(Point A, Point B, Point C){
	int o = orientation(A, B, C);
	return o < 0;
}

ll sq(ll x) { return x * x; }

Polygon convex_hull(Polygon &vec){
	Point root = *min_element(vec.begin(), vec.end());
	sort(vec.begin(), vec.end(), [&](const Point &A, const Point &B){
		int o = orientation(root, A, B);
		if (o == 0){
			return sq(root.x - A.x) + sq(root.y - A.y)
			< sq(root.x - B.x) + sq(root.y - B.y);
		}
		return o < 0;
	});

	Polygon res;
	for (int i = 0; i < (int)vec.size(); i++){
		while (res.size() > 1 && !cw(end(res)[-2], end(res)[-1], vec[i])){
			res.pop_back();
		}
		res.push_back(vec[i]);
	}

	return res;
}

struct Edge{
	int nxt;
	ll a, b;
};

int n, m;
ll A = 0, B = 0;
vector<int> depth, vst;
vector<vector<Edge>> adj;
vector<vector<Edge>> cycles;
vector<Edge> path;

void dfs(int x, int p = -1, int d = 0){
	depth[x] = d;
	vst[x] = 1;

	for (auto edge: adj[x]){
		int k = edge.nxt;
		if (k == p) continue;

		if (vst[k]){
			int diff = depth[x] - depth[k];
			if (diff > 0){
				cycles.emplace_back();
				cycles.back().push_back(edge);
				for (int i = 1; i <= diff; i++){
					cycles.back().push_back(end(path)[-i]);
				}
			}
		}
		else{
			path.push_back(edge);
			dfs(k, x, d+1);
			path.pop_back();
		}
	}
}

auto greater_by_size = [](const Polygon &p1, const Polygon &p2){
	return p1.size() > p2.size();
};
priority_queue<Polygon, vector<Polygon>, decltype(greater_by_size)> pq;

void main_program(){
	cin >> n >> m;

	depth.resize(n);
	vst.resize(n);
	adj.resize(n);

	for (int i = 0; i < n; i++){
		int x, y, a, b; cin >> x >> y >> a >> b;
		x--; y--;
		adj[x].push_back(Edge{y, a, b});
		adj[y].push_back(Edge{x, a, b});
		A += a; B += b;
	}

	dfs(0);

	for (auto cyc: cycles){
		Polygon crr;
		for (auto edge: cyc){
			crr.emplace_back(edge.a, edge.b);
		}
		pq.push(convex_hull(crr));
	}

	while (pq.size() >= 2){
		Polygon p1 = pq.top(); pq.pop();
		Polygon p2 = pq.top(); pq.pop();
		Polygon pmerge = mincowski_sum(p1, p2);
		pq.push(pmerge);
	}

	Polygon final = pq.top();

	ll opt = 1e18;
	for (auto pt: final){
		opt = min(opt, (A - pt.x) * (B - pt.y));
	}

	cout << opt << "\n";
}

answer.code:159:69: error: no matching function for call to ‘std::priority_queue<std::vector<Point>, std::vector<std::vector<Point> >, <lambda(const Polygon&, const Polygon&)> >::priority_queue()’
  159 | priority_queue<Polygon, vector<Polygon>, decltype(greater_by_size)> pq;
      |                                                                     ^~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_queue.h:597:9: note: candidate: ‘template<class _InputIterator> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, _Sequence&&) [with _InputIterator = _InputIterator; _Tp = std::vector<Point>; _Sequence = std::vector<std::vector<Point> >; _Compare = <lambda(const Polygon&, const Polygon&)>]’
  597 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_queue.h:597:9: note:   template argument deduction/substitution failed:
answer.code:159:69: note:   candidate expects 4 arguments, 0 provided
  159 | priority_queue<Polygon, vector<Polygon>, decltype(greater_by_size)> pq;
      |                                                                     ^~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_queue.h:586:9: note: candidate: ‘template<class _InputIterator> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Sequence&) [with _InputIterator = _InputIterator; _Tp = std::vector<Point>; _Sequence = std::vector<std::vector<Point> >; _Compare = <lambda(const Polygon&, const Polygon&)>]’
  586 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_queue.h:586:9: note:   template argument deduction/substitution failed:
answer.code:159:69: note:   candidate expects 4 arguments, 0 provided
  159 | priority_queue<Polygon, vector<Polygon>, decltype(greater_by_size)> pq;
      |                                                                     ^~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_queue.h:554:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(std::priority_queue<_Tp, _Sequence, _Compare>&&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::vector<Point>; _Sequence = std::vector<std::vector<Point> >; _Compare = <lambda(const Polygon&, const Polygon&)>]’
  554 |         priority_queue(priority_queue&& __q, const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_queue.h:554:9: note:   template argument deduction/substitution failed:
answer.code:159:69: note:   candidate expects 2 arguments, 0 provided
  159 | priority_queue<Polygon, vector<Polygon>, decltype(greater_by_size)> pq;
      |                                                                     ^~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_queue.h:550:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const std::priority_queue<_Tp, _Sequence, _Compare>&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::vector<Point>; _Sequence = std::vector<std::vector<Point> >; _Compare = <lambda(const Polygon&, const Polygon&)>]’
  550 |         priority_queue(const priority_queue& __q, const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_queue.h:550:9: note:   template argument deduction/substitution failed:
answer.code:159:69: note:   candidate expects 2 arguments, 0 provided
  159 | priority_queue<Polygon, vector<Polygon>, decltype(greater_by_size)> pq;
      |                                                                     ^~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_queue.h:545:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::vector<Point>; _Sequence = std::vector<std::vector<Point> >; _Compare = <lambda(const Polygon&, const Polygon&)>]’
  545 |         priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
      |         ^~~~~~...