Project Selection（燃やす埋める）

graph/project_selection.hpp · GitHub で見る

共通ページ

各頂点を選ぶ・選ばないの 2 通りに分け、費用の総和を最小化します。利益は負の費用として加えます。選択を true（1、燃やす）、非選択を false（0、埋める）とします。反転を指定しない頂点では、最小カットの始点側が選択側です。

費用・利益には負の値も指定できます。ただし、add_penalty・add_difference_cost・add_same_cost・add_same_profit・add_difference_profit・add_all_profit・add_any_cost に渡す金額は非負にしてください。二変数項には、さらに後述の条件があります。

#include "lib/graph/project_selection.hpp"
#include <cassert>

ProjectSelection<> problem(2);
problem.add_profit(0, 10); // 0 を選ぶと利益 10
problem.add_cost(1, 4);    // 1 を選ぶと費用 4
problem.imply(0, 1);       // 0 を選ぶなら 1 も選ぶ

auto result = problem.solve();
assert(result && result->profit() == 6);
assert(result->cost == -6);
assert(result->selected[0] && result->selected[1]);

操作	内容・返り値	追加時の計算量
`ProjectSelection<Cost = std::int64_t>(n = 0)`	`n` 頂点の問題を作る。頂点番号は `[0,n)`	\(O(n)\)
`ProjectSelection(n,flipped)`	長さ `n` の `vector<bool>` で、内部の選択を反転する頂点を指定する	\(O(n)\)
`size()`	利用者が指定した頂点数。内部の補助頂点は含まない	\(O(1)\)
`is_flipped(v)`	頂点 `v` の反転指定を返す	\(O(1)\)
`add_constant(cost)`	選択によらない費用を加える	\(O(1)\)
`add_cost(v,cost)`	`v` を選ぶ場合に費用を加える	\(O(1)\)
`add_cost(v,c0,c1)`	`v` を選ばない場合に `c0`、選ぶ場合に `c1` を加える	\(O(1)\)
`add_profit(v,profit)`	`v` を選ぶ場合に利益を加える	\(O(1)\)
`add_profit(v,p0,p1)`	`v` を選ばない場合に `p0`、選ぶ場合に `p1` の利益を加える	\(O(1)\)
`add_cost_if(v,value,cost)`	`v` の選択が `value` の場合だけ費用を加える	\(O(1)\)
`add_profit_if(v,value,profit)`	`v` の選択が `value` の場合だけ利益を加える	\(O(1)\)
`add_cost_if(u,v,a,b,cost)`	選択 `(u,v)` が `(a,b)` の場合だけ費用を加える	償却 \(O(1)\)
`add_profit_if(u,v,a,b,profit)`	選択 `(u,v)` が `(a,b)` の場合だけ利益を加える	償却 \(O(1)\)
`add_penalty(u,v,cost)`	`u` を選び `v` を選ばない場合だけ費用を加える	償却 \(O(1)\)
`add_difference_cost(u,v,cost)`	`u`・`v` の選択が異なる場合に費用を加える	償却 \(O(1)\)
`add_same_cost(u,v,cost)`	`u`・`v` の選択が同じ場合に費用を加える	償却 \(O(1)\)
`add_same_profit(u,v,profit)`	`u`・`v` の選択が同じ場合に利益を加える	償却 \(O(1)\)
`add_difference_profit(u,v,profit)`	`u`・`v` の選択が異なる場合に利益を加える	償却 \(O(1)\)
`add_pair_cost(u,v,c00,c01,c10,c11)`	選択 `(u,v)` が `00,01,10,11` の各場合の費用を加える。下記の条件が必要	償却 \(O(1)\)
`add_pair_profit(u,v,p00,p01,p10,p11)`	選択 `(u,v)` が `00,01,10,11` の各場合の利益を加える。下記の条件が必要	償却 \(O(1)\)
`add_all_profit(vertices,value,profit)`	指定した全頂点の選択が `value` と一致する場合だけ利益を加える	償却 \(O(k)\)
`add_any_cost(vertices,value,cost)`	指定した頂点のうち少なくとも 1 つの選択が `value` と一致する場合に、費用を 1 回だけ加える	償却 \(O(k)\)
`force(v,value)`	`v` の選択を `value` に固定する	償却 \(O(1)\)
`imply(u,v)`	`u` を選ぶなら `v` も選ぶという制約を加える	償却 \(O(1)\)
`imply(u,v,a,b)`	`u` の選択が `a` なら `v` の選択が `b` という制約を加える	償却 \(O(1)\)
`forbid(u,v,a,b)`	選択 `(u,v)` が `(a,b)` となることを禁止する	償却 \(O(1)\)
`same(u,v)`	`u` と `v` の選択を一致させる	償却 \(O(1)\)
`different(u,v)`	`u` と `v` の選択を異ならせる	償却 \(O(1)\)
`at_most_one(u,v)`	両方を選ぶことを禁止する	償却 \(O(1)\)
`at_least_one(u,v)`	少なくとも片方を選ぶことを必須にする	償却 \(O(1)\)
`solve()`	最小費用と選択を `optional<Result>` で返す。実行不能なら `nullopt`	最大流の計算量

Cost は符号付き 64 bit 以下の標準整数型です。呼び出した項は全て加算され、既存の項を上書きしません。Result::cost は最小費用、profit() はその符号を反転した最大純利益、selected は長さ n の vector<bool> です。費用の合計には __int128_t を使い、total_type で参照できます。出力には FastOutput が使えます。

solve() は問題を変更しません。繰り返し呼べ、求解後に項や制約を追加した場合は、次の solve() で再構築して解きます。コピーした問題は独立に変更できます。最適解が複数ある場合はそのうち 1 つを返します。

反転は構築時に指定し、問題の途中では変更しません。flipped[v] == true の頂点では、内部の変数を元の選択と逆向きに扱います。費用・利益・制約の引数と Result::selected は、全て元の選択の意味です。例えば force(v,true) は、反転指定によらず元の頂点を選ぶという制約です。

二変数コストは、反転後の表で劣モジュラ条件を満たす必要があります。元の選択に対する費用の条件は次の通りです。add_pair_profit は、利益の符号を反転して同じ条件を判定します。

`u`・`v` の反転指定	二変数コストの条件
同じ	\(c_{00}+c_{11}\leq c_{01}+c_{10}\)
異なる	\(c_{00}+c_{11}\geq c_{01}+c_{10}\)

add_cost_if・add_profit_if の二変数版にも同じ条件が適用されます。正の罰金なら、反転後の指定状態が異なる場合に使えます。正の報酬なら、反転後の指定状態が同じ場合に使えます。負の額を指定すると、許される指定状態も逆になります。額が 0 なら反転の制約はありません。

例えば、二部グラフの辺ごとに「両方を燃やすと罰金」「両方を埋めると罰金」を加える場合、片側だけを反転します。次の 0,2 と 1,3 が二部に分かれています。

ProjectSelection<> problem(4, {false, true, false, true});
problem.add_cost_if(0, true, 3);          // 0 を燃やすと罰金 3
problem.add_cost_if(1, false, 5);         // 1 を埋めると罰金 5
problem.add_cost_if(0, 1, true, true, 7); // 両方を燃やすと罰金 7
problem.add_cost_if(2, 3, false, false, 4); // 両方を埋めると罰金 4
problem.add_all_profit({0, 2}, true, 11); // 両方を燃やすと報酬 11
problem.add_all_profit({1, 3}, false, 8); // 両方を埋めると報酬 8
problem.at_most_one(0, 1);              // 同時には選べない
problem.at_least_one(2, 3);             // 少なくとも一方を選ぶ
auto answer = problem.solve();

燃やす・埋めるの代表的な条件は、以下の操作で表せます。金額 P は正とします。

条件	操作	反転指定の条件
`u` を燃やすと罰金	`add_cost_if(u,true,P)`	任意
`u` を埋めると罰金	`add_cost_if(u,false,P)`	任意
`u` を燃やし `v` を埋めると罰金	`add_cost_if(u,v,true,false,P)`	`u`・`v` で同じ
両方を燃やすと罰金	`add_cost_if(u,v,true,true,P)`	`u`・`v` で異なる
両方を埋めると罰金	`add_cost_if(u,v,false,false,P)`	`u`・`v` で異なる
選択が同じなら罰金	`add_same_cost(u,v,P)`	`u`・`v` で異なる
選択が異なるなら罰金	`add_difference_cost(u,v,P)`	`u`・`v` で同じ
選択が同じなら報酬	`add_same_profit(u,v,P)`	`u`・`v` で同じ
選択が異なるなら報酬	`add_difference_profit(u,v,P)`	`u`・`v` で異なる
全員を燃やす／埋めると報酬	`add_all_profit(vertices,value,P)`	列内の反転指定が全て同じ
一人でも燃やす／埋めると罰金	`add_any_cost(vertices,value,P)`	列内の反転指定が全て同じ

同じ問題に追加する全ての項・制約が、同一の反転指定で条件を満たす必要があります。任意の二変数コストや、二部に分けられないグラフ上の「同じ選択なら罰金」を扱えるわけではありません。反転は呼び出しごとに独立に行うものではありません。

add_all_profit は、全員を選ぶ場合と全員を選ばない場合の両方に使えます。空の頂点列では常に利益を得ます。重複頂点を渡しても条件の意味は変わりませんが、処理量は重複を含む長さ k に比例します。補助頂点は最大 1 個、辺は最大 k 本追加します。

add_any_cost は、誰も指定状態でなければ費用を加えず、1 人以上なら人数によらず 1 回だけ費用を加えます。空の頂点列では常に費用 0 です。両関数とも、正の額を指定して列に 2 項目以上ある場合は、列内の反転指定を全て同じにしてください。列が空または 1 項目の場合、この条件は不要です。

ProjectSelection<> model(3);
model.add_all_profit({0, 1, 2}, true, 20); // 全員を選ぶと利益 20
model.add_all_profit({0, 1}, false, 7);   // 両方を選ばないと利益 7
model.add_penalty(0, 2, 5);              // 0 だけを選ぶと費用 5
model.force(1, false);
auto answer = model.solve();

依存関係は閉路を持っていても構いません。必須・禁止などの矛盾は、制約辺だけで始点から終点へ到達できるかを調べて判定します。「無限大」の値は利用者が指定せず、有限容量の総和より 1 大きい値を内部で設定します。

forbid(u,v,a,b) は、反転後の a と b が異なる場合に使えます。imply(u,v,a,b) は、反転後の a と b が同じ場合に使えます。従って same・二引数の imply は両頂点の反転指定が同じ場合、different・at_most_one・at_least_one は異なる場合に使えます。対応しない項・制約の追加は入力条件違反として assert で検査し、実行不能を返す nullopt とは区別します。

u == v の二変数コスト・利益は 00 と 11 だけを使い、劣モジュラ条件は不要です。指定状態の二変数費用・利益で同じ頂点へ異なる状態を指定した場合は、常に寄与 0 です。forbid(v,v,a,b) も a != b なら制約なし、a == b ならその状態を禁止します。different(v,v) は実行不能、at_most_one(v,v) は非選択への固定、at_least_one(v,v) は選択への固定です。

各頂点の一変数項は差分へ集約します。その差分の絶対値と、変換後の有限容量辺の容量の総和を \(B\) として、\(B<2^{64}-1\) が必要です。二変数項から作る容量にも符号なし 64 bit を使います。項の集約・定数項・最終費用の計算途中は符号付き 128 bit に収めてください。補助頂点を含む変数数は INT_MAX/2-3 以下、始点・終点を含む全辺数は INT_MAX/2 以下とします。これらの条件は入力の前提で、実行不能を表す nullopt とは区別します。

元の頂点数を \(n\)、補助頂点・始点・終点を含む頂点数を \(V\)、一変数項の集約後の辺数を \(E\) とします。構築は \(O(n)\) 時間・空間、項と制約の保持は \(O(V+E)\) 空間です。solve() はグラフの構築・制約の矛盾判定・解の復元に \(O(V+E)\) 時間、最大流に一般の上界で \(O(V^2E)\) 時間、追加空間は \(O(V+E)\) です。

依存ライブラリ

コード

#line 1 "graph/project_selection.hpp"

#line 1 "graph/max_flow.hpp"

#line 1 "components/flow_graph.hpp"

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

namespace flow_detail {
template<class Cap> struct Graph {
	struct Arc { int to; Cap cap; };
	int n;
	std::vector<Arc> arcs;
	std::vector<int> start, order;
	bool built = false;
	explicit Graph(int n = 0) : n(n) { assert(n >= 0); }
	void reserve(std::size_t m) { assert(m <= std::size_t(std::numeric_limits<int>::max() / 2)); arcs.reserve(2 * m); }
	int add_edge(int from, int to, Cap cap) {
		assert(0 <= from && from < n && 0 <= to && to < n && cap >= 0);
		assert(arcs.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
		int id = int(arcs.size());
		arcs.push_back({to, cap});
		arcs.push_back({from, Cap(0)});
		built = false;
		return id / 2;
	}
	void build() {
		if (built) return;
		start.assign(std::size_t(n) + 1, 0);
		for (std::size_t i = 0; i < arcs.size(); ++i) ++start[arcs[i ^ 1].to + 1];
		for (int v = 0; v < n; ++v) start[v + 1] += start[v];
		order.resize(arcs.size());
		auto next = start;
		for (int i = 0; i < int(arcs.size()); ++i) order[next[arcs[i ^ 1].to]++] = i;
		built = true;
	}
	void reset_flow() {
		for (std::size_t i = 0; i < arcs.size(); i += 2) arcs[i].cap += arcs[i + 1].cap, arcs[i + 1].cap = 0;
	}
};
}

#line 1 "components/push_relabel.hpp"

#line 5 "components/push_relabel.hpp"
#include <cstdint>

namespace flow_detail {
template<class Cap> Cap push_relabel(Graph<Cap>& graph, int s, int t) {
	graph.build();
	int n = graph.n;
	assert(n <= std::numeric_limits<int>::max() / 2 - 1);
	int dead = 2 * n;
	std::vector<__uint128_t> excess(n);
	std::vector<int> height(n), current(n), count(std::size_t(dead) + 1), head(std::size_t(dead) + 1, -1), next(n), queue(n);
	std::vector<unsigned char> active(n);
	int highest = -1;
	std::size_t work = 0, threshold = std::max<std::size_t>(1, 4 * graph.arcs.size() + n);
	auto activate = [&](int v) {
		if (v == s || v == t || active[v] || !excess[v] || height[v] == dead) return;
		active[v] = 1;
		next[v] = head[height[v]], head[height[v]] = v;
		highest = std::max(highest, height[v]);
	};
	auto buckets = [&] {
		std::fill(head.begin(), head.end(), -1);
		std::fill(active.begin(), active.end(), 0);
		highest = -1;
		for (int v = 0; v < n; ++v) activate(v);
	};
	auto global = [&] {
		std::fill(height.begin(), height.end(), n + 1);
		std::fill(count.begin(), count.end(), 0);
		std::copy_n(graph.start.begin(), n, current.begin());
		height[s] = n, height[t] = 0;
		int first = 0, last = 0;
		queue[last++] = t;
		while (first < last) {
			int v = queue[first++];
			for (int j = graph.start[v]; j < graph.start[v + 1]; ++j) {
				int i = graph.order[j], u = graph.arcs[i].to;
				if (u != s && height[u] == n + 1 && graph.arcs[i ^ 1].cap) height[u] = height[v] + 1, queue[last++] = u;
			}
		}
		for (int h : height) ++count[h];
		buckets();
		work = 0;
	};
	for (int j = graph.start[s]; j < graph.start[s + 1]; ++j) {
		int i = graph.order[j];
		auto& e = graph.arcs[i];
		if (e.to == s || !e.cap) continue;
		excess[e.to] += e.cap, graph.arcs[i ^ 1].cap += e.cap, e.cap = 0;
	}
	global();
	while (highest >= 0) {
		if (head[highest] < 0) { --highest; continue; }
		int v = head[highest];
		head[highest] = next[v];
		if (!active[v] || height[v] != highest) continue;
		active[v] = 0;
		while (excess[v] && height[v] < dead) {
			if (current[v] == graph.start[v + 1]) {
				int old = height[v], value = dead;
				for (int j = graph.start[v]; j < graph.start[v + 1]; ++j) {
					const auto& e = graph.arcs[graph.order[j]];
					if (e.cap) value = std::min(value, height[e.to] + 1);
				}
				work += graph.start[v + 1] - graph.start[v];
				--count[old], ++count[value], height[v] = value, current[v] = graph.start[v];
				if (old < n && !count[old]) {
					for (int u = 0; u < n; ++u) if (old < height[u] && height[u] < n) {
						--count[height[u]], height[u] = n + 1, ++count[n + 1], current[u] = graph.start[u];
					}
					buckets();
					break;
				}
			} else {
				++work;
				int i = graph.order[current[v]];
				auto& e = graph.arcs[i];
				if (!e.cap || height[v] != height[e.to] + 1) { ++current[v]; continue; }
				Cap amount = Cap(std::min(excess[v], __uint128_t(e.cap)));
				e.cap -= amount, graph.arcs[i ^ 1].cap += amount;
				excess[v] -= amount, excess[e.to] += amount;
				activate(e.to);
			}
		}
		activate(v);
		if (work >= threshold) global();
	}
	assert(excess[t] <= __uint128_t(std::numeric_limits<Cap>::max()));
	return Cap(excess[t]);
}
}

#line 7 "graph/max_flow.hpp"
#include <type_traits>

template<class Cap = std::int64_t> class MaxFlow {
	static_assert(std::is_integral_v<Cap> && !std::is_same_v<Cap, bool> && sizeof(Cap) <= 8);
	flow_detail::Graph<Cap> graph_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < graph_.n); }
	int index(int i) const { assert(0 <= i && std::size_t(i) < graph_.arcs.size() / 2); return 2 * i; }

public:
	struct Edge { int from, to; Cap cap, flow; };
	explicit MaxFlow(int n = 0) : graph_(n) {}
	int size() const { return graph_.n; }
	int edge_count() const { return int(graph_.arcs.size() / 2); }
	void reserve(std::size_t m) { graph_.reserve(m); }
	int add_edge(int from, int to, Cap cap) { return graph_.add_edge(from, to, cap); }
	Edge get_edge(int i) const {
		int j = index(i);
		const auto& a = graph_.arcs[j];
		const auto& b = graph_.arcs[j ^ 1];
		return {b.to, a.to, Cap(a.cap + b.cap), b.cap};
	}
	std::vector<Edge> edges() const {
		std::vector<Edge> result;
		result.reserve(edge_count());
		for (int i = 0; i < edge_count(); ++i) result.push_back(get_edge(i));
		return result;
	}
	void change_edge(int i, Cap cap, Cap flow) {
		assert(0 <= flow && flow <= cap);
		int j = index(i);
		graph_.arcs[j].cap = cap - flow, graph_.arcs[j ^ 1].cap = flow;
	}
	void reset_flow() { graph_.reset_flow(); }
	Cap flow(int s, int t) {
		vertex(s), vertex(t);
		assert(s != t);
		return flow_detail::push_relabel(graph_, s, t);
	}
	Cap flow(int s, int t, Cap limit) {
		vertex(s), vertex(t);
		assert(s != t && limit >= 0);
		graph_.build();
		auto& g = graph_;
		std::vector<int> level(g.n), iter(g.n), queue(g.n);
		struct Frame { int v; Cap limit, sent; };
		std::vector<Frame> stack;
		stack.reserve(g.n);
		Cap total = 0;
		while (total < limit) {
			std::fill(level.begin(), level.end(), -1);
			level[s] = 0;
			int head = 0, tail = 0;
			queue[tail++] = s;
			while (head < tail && level[t] < 0) {
				int v = queue[head++];
				for (int i = g.start[v]; i < g.start[v + 1]; ++i) {
					const auto& e = g.arcs[g.order[i]];
					if (!e.cap || level[e.to] >= 0) continue;
					level[e.to] = level[v] + 1;
					queue[tail++] = e.to;
				}
			}
			if (level[t] < 0) break;
			std::copy_n(g.start.begin(), g.n, iter.begin());
			stack.push_back({t, Cap(limit - total), Cap(0)});
			while (!stack.empty()) {
				auto& frame = stack.back();
				int v = frame.v;
				if (v == s || frame.sent == frame.limit || iter[v] == g.start[v + 1]) {
					Cap sent = v == s ? frame.limit : frame.sent;
					if (v != s && sent < frame.limit) level[v] = g.n;
					stack.pop_back();
					if (stack.empty()) { total += sent; break; }
					auto& parent = stack.back();
					int id = g.order[iter[parent.v]];
					g.arcs[id].cap += sent, g.arcs[id ^ 1].cap -= sent;
					parent.sent += sent;
					if (parent.sent < parent.limit) ++iter[parent.v];
				} else {
					int id = g.order[iter[v]];
					const auto& e = g.arcs[id];
					if (level[e.to] < 0 || level[e.to] >= level[v] || !g.arcs[id ^ 1].cap) ++iter[v];
					else stack.push_back({e.to, std::min<Cap>(frame.limit - frame.sent, g.arcs[id ^ 1].cap), Cap(0)});
				}
			}
		}
		return total;
	}
	std::vector<bool> min_cut(int s) {
		vertex(s);
		graph_.build();
		std::vector<bool> visited(graph_.n);
		std::vector<int> queue{ s };
		visited[s] = true;
		for (std::size_t head = 0; head < queue.size(); ++head) {
			int v = queue[head];
			for (int i = graph_.start[v]; i < graph_.start[v + 1]; ++i) {
				const auto& e = graph_.arcs[graph_.order[i]];
				if (e.cap && !visited[e.to]) visited[e.to] = true, queue.push_back(e.to);
			}
		}
		return visited;
	}
};

#line 5 "graph/project_selection.hpp"
#include <array>
#line 10 "graph/project_selection.hpp"
#include <optional>
#line 12 "graph/project_selection.hpp"
#include <utility>
#line 14 "graph/project_selection.hpp"

template<class Cost = std::int64_t> class ProjectSelection {
	static_assert(std::is_integral_v<Cost> && std::is_signed_v<Cost> && sizeof(Cost) <= 8);
	using Wide = __int128_t;
	using Cap = std::uint64_t;
	struct Edge { int from, to; Cap cost; };
	int n_;
	Wide constant_ = 0;
	std::vector<Wide> unary_;
	std::vector<bool> flipped_;
	std::vector<Edge> edges_;
	std::vector<std::pair<int, int>> hard_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < n_); }
	bool orientation(int v) const { return !flipped_.empty() && flipped_[v]; }
	void unary(int v, Wide c0, Wide c1) {
		vertex(v);
		if (orientation(v)) std::swap(c0, c1);
		constant_ += c0;
		unary_[v] += c1 - c0;
	}
	static Cap capacity(Wide cost) {
		assert(0 <= cost && cost <= std::numeric_limits<Cap>::max());
		return static_cast<Cap>(cost);
	}
	void penalty(int from, int to, Wide cost) {
		assert(cost >= 0);
		if (cost && from != to) edges_.push_back({from, to, capacity(cost)});
	}
	void pair(int u, int v, std::array<Wide, 4> cost) {
		vertex(u), vertex(v);
		if (u == v) { unary(u, cost[0], cost[3]); return; }
		if (orientation(u)) std::swap(cost[0], cost[2]), std::swap(cost[1], cost[3]);
		if (orientation(v)) std::swap(cost[0], cost[1]), std::swap(cost[2], cost[3]);
		Wide delta = cost[1] + cost[2] - cost[0] - cost[3];
		assert(delta >= 0);
		constant_ += cost[0];
		unary_[u] += cost[3] - cost[1];
		unary_[v] += cost[1] - cost[0];
		penalty(u, v, delta);
	}
	void condition(int u, int v, bool u_value, bool v_value, Wide cost) {
		vertex(u), vertex(v);
		if (u == v) {
			if (u_value == v_value) unary(u, u_value ? 0 : cost, u_value ? cost : 0);
			return;
		}
		if (cost >= 0) {
			u_value = u_value != orientation(u), v_value = v_value != orientation(v);
			assert(!cost || u_value != v_value);
			penalty(u_value ? u : v, u_value ? v : u, cost);
			return;
		}
		std::array<Wide, 4> table{};
		table[2 * int(u_value) + int(v_value)] = cost;
		pair(u, v, table);
	}
	int auxiliary() {
		assert(unary_.size() < std::size_t(std::numeric_limits<int>::max() / 2 - 3));
		int v = static_cast<int>(unary_.size());
		unary_.push_back(0);
		return v;
	}

public:
	using cost_type = Cost;
	using total_type = Wide;
	struct Result {
		Wide cost;
		std::vector<bool> selected;
		Wide profit() const { return -cost; }
	};
	explicit ProjectSelection(int n = 0) : n_(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2 - 3);
		unary_.resize(n);
	}
	ProjectSelection(int n, const std::vector<bool> &flipped) : ProjectSelection(n) {
		assert(flipped.size() == std::size_t(n));
		flipped_ = flipped;
	}
	int size() const { return n_; }
	bool is_flipped(int v) const { vertex(v); return orientation(v); }
	void add_constant(Cost cost) { constant_ += Wide(cost); }
	void add_cost(int v, Cost cost) { unary(v, 0, Wide(cost)); }
	void add_cost(int v, Cost false_cost, Cost true_cost) { unary(v, Wide(false_cost), Wide(true_cost)); }
	void add_profit(int v, Cost profit) { unary(v, 0, -Wide(profit)); }
	void add_profit(int v, Cost false_profit, Cost true_profit) { unary(v, -Wide(false_profit), -Wide(true_profit)); }
	void add_cost_if(int v, bool value, Cost cost) { unary(v, value ? 0 : Wide(cost), value ? Wide(cost) : 0); }
	void add_profit_if(int v, bool value, Cost profit) { unary(v, value ? 0 : -Wide(profit), value ? -Wide(profit) : 0); }
	void add_cost_if(int u, int v, bool u_value, bool v_value, Cost cost) {
		condition(u, v, u_value, v_value, Wide(cost));
	}
	void add_profit_if(int u, int v, bool u_value, bool v_value, Cost profit) {
		condition(u, v, u_value, v_value, -Wide(profit));
	}
	void add_penalty(int u, int v, Cost cost) {
		assert(cost >= 0);
		add_cost_if(u, v, true, false, cost);
	}
	void add_difference_cost(int u, int v, Cost cost) {
		vertex(u), vertex(v);
		assert(cost >= 0 && (u == v || !cost || orientation(u) == orientation(v)));
		penalty(u, v, Wide(cost));
		penalty(v, u, Wide(cost));
	}
	void add_same_cost(int u, int v, Cost cost) {
		vertex(u), vertex(v);
		assert(cost >= 0);
		if (u == v) { constant_ += Wide(cost); return; }
		assert(!cost || orientation(u) != orientation(v));
		penalty(u, v, Wide(cost));
		penalty(v, u, Wide(cost));
	}
	void add_same_profit(int u, int v, Cost profit) {
		assert(profit >= 0);
		add_difference_cost(u, v, profit);
		constant_ -= Wide(profit);
	}
	void add_difference_profit(int u, int v, Cost profit) {
		assert(profit >= 0);
		add_same_cost(u, v, profit);
		constant_ -= Wide(profit);
	}
	void add_pair_cost(int u, int v, Cost c00, Cost c01, Cost c10, Cost c11) {
		pair(u, v, {Wide(c00), Wide(c01), Wide(c10), Wide(c11)});
	}
	void add_pair_profit(int u, int v, Cost p00, Cost p01, Cost p10, Cost p11) {
		pair(u, v, {-Wide(p00), -Wide(p01), -Wide(p10), -Wide(p11)});
	}
	void add_all_profit(const std::vector<int> &vertices, bool value, Cost profit) {
		assert(profit >= 0);
		for ([[maybe_unused]] int v : vertices) vertex(v);
		if (!profit) return;
		if (vertices.empty()) { constant_ -= Wide(profit); return; }
		if (vertices.size() == 1) {
			add_profit_if(vertices[0], value, profit);
			return;
		}
		for ([[maybe_unused]] int v : vertices) assert(orientation(v) == orientation(vertices[0]));
		value = value != orientation(vertices[0]);
		int aux = auxiliary();
		if (value) unary_[aux] -= Wide(profit);
		else constant_ -= Wide(profit), unary_[aux] += Wide(profit);
		for (int v : vertices) {
			if (value) penalty(aux, v, Wide(profit));
			else penalty(v, aux, Wide(profit));
		}
	}
	void add_any_cost(const std::vector<int> &vertices, bool value, Cost cost) {
		assert(cost >= 0);
		add_all_profit(vertices, !value, cost);
		constant_ += Wide(cost);
	}
	void force(int v, bool value) {
		vertex(v);
		value = value != orientation(v);
		hard_.emplace_back(value ? -1 : v, value ? v : -2);
	}
	void forbid(int u, int v, bool u_value, bool v_value) {
		vertex(u), vertex(v);
		if (u == v) {
			if (u_value == v_value) force(u, !u_value);
			return;
		}
		u_value = u_value != orientation(u), v_value = v_value != orientation(v);
		assert(u_value != v_value);
		hard_.emplace_back(u_value ? u : v, u_value ? v : u);
	}
	void imply(int u, int v) { forbid(u, v, true, false); }
	void imply(int u, int v, bool u_value, bool v_value) { forbid(u, v, u_value, !v_value); }
	void same(int u, int v) { imply(u, v); imply(v, u); }
	void different(int u, int v) { forbid(u, v, false, false); forbid(u, v, true, true); }
	void at_most_one(int u, int v) { forbid(u, v, true, true); }
	void at_least_one(int u, int v) { forbid(u, v, false, false); }
	std::optional<Result> solve() const {
		Wide bound = 0, base = constant_;
		std::size_t count = edges_.size() + hard_.size();
		for (const auto &edge : edges_) bound += Wide(edge.cost);
		for (Wide cost : unary_) {
			bound += cost < 0 ? -cost : cost;
			count += cost != 0;
			if (cost < 0) base += cost;
		}
		assert(bound < Wide(std::numeric_limits<Cap>::max()));
		const Cap infinity = capacity(bound + 1);
		const int source = static_cast<int>(unary_.size()), sink = source + 1;
		MaxFlow<Cap> graph(source + 2);
		graph.reserve(count);
		auto endpoint = [&](int v) { return v == -1 ? source : v == -2 ? sink : v; };
		for (auto [u, v] : hard_) graph.add_edge(endpoint(u), endpoint(v), infinity);
		if (!hard_.empty() && graph.min_cut(source)[sink]) return std::nullopt;
		for (const auto &edge : edges_) graph.add_edge(edge.from, edge.to, edge.cost);
		for (int v = 0; v < source; ++v) {
			if (unary_[v] < 0) graph.add_edge(source, v, capacity(-unary_[v]));
			else if (unary_[v] > 0) graph.add_edge(v, sink, capacity(unary_[v]));
		}
		Wide cost = base + Wide(graph.flow(source, sink));
		auto selected = graph.min_cut(source);
		selected.resize(n_);
		if (!flipped_.empty()) for (int v = 0; v < n_; ++v) selected[v] = selected[v] != flipped_[v];
		return Result{cost, std::move(selected)};
	}
};

#ifndef PROJECT_SELECTION_HPP
#define PROJECT_SELECTION_HPP

#include "max_flow.hpp"
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template<class Cost = std::int64_t> class ProjectSelection {
	static_assert(std::is_integral_v<Cost> && std::is_signed_v<Cost> && sizeof(Cost) <= 8);
	using Wide = __int128_t;
	using Cap = std::uint64_t;
	struct Edge { int from, to; Cap cost; };
	int n_;
	Wide constant_ = 0;
	std::vector<Wide> unary_;
	std::vector<bool> flipped_;
	std::vector<Edge> edges_;
	std::vector<std::pair<int, int>> hard_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < n_); }
	bool orientation(int v) const { return !flipped_.empty() && flipped_[v]; }
	void unary(int v, Wide c0, Wide c1) {
		vertex(v);
		if (orientation(v)) std::swap(c0, c1);
		constant_ += c0;
		unary_[v] += c1 - c0;
	}
	static Cap capacity(Wide cost) {
		assert(0 <= cost && cost <= std::numeric_limits<Cap>::max());
		return static_cast<Cap>(cost);
	}
	void penalty(int from, int to, Wide cost) {
		assert(cost >= 0);
		if (cost && from != to) edges_.push_back({from, to, capacity(cost)});
	}
	void pair(int u, int v, std::array<Wide, 4> cost) {
		vertex(u), vertex(v);
		if (u == v) { unary(u, cost[0], cost[3]); return; }
		if (orientation(u)) std::swap(cost[0], cost[2]), std::swap(cost[1], cost[3]);
		if (orientation(v)) std::swap(cost[0], cost[1]), std::swap(cost[2], cost[3]);
		Wide delta = cost[1] + cost[2] - cost[0] - cost[3];
		assert(delta >= 0);
		constant_ += cost[0];
		unary_[u] += cost[3] - cost[1];
		unary_[v] += cost[1] - cost[0];
		penalty(u, v, delta);
	}
	void condition(int u, int v, bool u_value, bool v_value, Wide cost) {
		vertex(u), vertex(v);
		if (u == v) {
			if (u_value == v_value) unary(u, u_value ? 0 : cost, u_value ? cost : 0);
			return;
		}
		if (cost >= 0) {
			u_value = u_value != orientation(u), v_value = v_value != orientation(v);
			assert(!cost || u_value != v_value);
			penalty(u_value ? u : v, u_value ? v : u, cost);
			return;
		}
		std::array<Wide, 4> table{};
		table[2 * int(u_value) + int(v_value)] = cost;
		pair(u, v, table);
	}
	int auxiliary() {
		assert(unary_.size() < std::size_t(std::numeric_limits<int>::max() / 2 - 3));
		int v = static_cast<int>(unary_.size());
		unary_.push_back(0);
		return v;
	}

  public:
	using cost_type = Cost;
	using total_type = Wide;
	struct Result {
		Wide cost;
		std::vector<bool> selected;
		Wide profit() const { return -cost; }
	};
	explicit ProjectSelection(int n = 0) : n_(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2 - 3);
		unary_.resize(n);
	}
	ProjectSelection(int n, const std::vector<bool> &flipped) : ProjectSelection(n) {
		assert(flipped.size() == std::size_t(n));
		flipped_ = flipped;
	}
	int size() const { return n_; }
	bool is_flipped(int v) const { vertex(v); return orientation(v); }
	void add_constant(Cost cost) { constant_ += Wide(cost); }
	void add_cost(int v, Cost cost) { unary(v, 0, Wide(cost)); }
	void add_cost(int v, Cost false_cost, Cost true_cost) { unary(v, Wide(false_cost), Wide(true_cost)); }
	void add_profit(int v, Cost profit) { unary(v, 0, -Wide(profit)); }
	void add_profit(int v, Cost false_profit, Cost true_profit) { unary(v, -Wide(false_profit), -Wide(true_profit)); }
	void add_cost_if(int v, bool value, Cost cost) { unary(v, value ? 0 : Wide(cost), value ? Wide(cost) : 0); }
	void add_profit_if(int v, bool value, Cost profit) { unary(v, value ? 0 : -Wide(profit), value ? -Wide(profit) : 0); }
	void add_cost_if(int u, int v, bool u_value, bool v_value, Cost cost) {
		condition(u, v, u_value, v_value, Wide(cost));
	}
	void add_profit_if(int u, int v, bool u_value, bool v_value, Cost profit) {
		condition(u, v, u_value, v_value, -Wide(profit));
	}
	void add_penalty(int u, int v, Cost cost) {
		assert(cost >= 0);
		add_cost_if(u, v, true, false, cost);
	}
	void add_difference_cost(int u, int v, Cost cost) {
		vertex(u), vertex(v);
		assert(cost >= 0 && (u == v || !cost || orientation(u) == orientation(v)));
		penalty(u, v, Wide(cost));
		penalty(v, u, Wide(cost));
	}
	void add_same_cost(int u, int v, Cost cost) {
		vertex(u), vertex(v);
		assert(cost >= 0);
		if (u == v) { constant_ += Wide(cost); return; }
		assert(!cost || orientation(u) != orientation(v));
		penalty(u, v, Wide(cost));
		penalty(v, u, Wide(cost));
	}
	void add_same_profit(int u, int v, Cost profit) {
		assert(profit >= 0);
		add_difference_cost(u, v, profit);
		constant_ -= Wide(profit);
	}
	void add_difference_profit(int u, int v, Cost profit) {
		assert(profit >= 0);
		add_same_cost(u, v, profit);
		constant_ -= Wide(profit);
	}
	void add_pair_cost(int u, int v, Cost c00, Cost c01, Cost c10, Cost c11) {
		pair(u, v, {Wide(c00), Wide(c01), Wide(c10), Wide(c11)});
	}
	void add_pair_profit(int u, int v, Cost p00, Cost p01, Cost p10, Cost p11) {
		pair(u, v, {-Wide(p00), -Wide(p01), -Wide(p10), -Wide(p11)});
	}
	void add_all_profit(const std::vector<int> &vertices, bool value, Cost profit) {
		assert(profit >= 0);
		for ([[maybe_unused]] int v : vertices) vertex(v);
		if (!profit) return;
		if (vertices.empty()) { constant_ -= Wide(profit); return; }
		if (vertices.size() == 1) {
			add_profit_if(vertices[0], value, profit);
			return;
		}
		for ([[maybe_unused]] int v : vertices) assert(orientation(v) == orientation(vertices[0]));
		value = value != orientation(vertices[0]);
		int aux = auxiliary();
		if (value) unary_[aux] -= Wide(profit);
		else constant_ -= Wide(profit), unary_[aux] += Wide(profit);
		for (int v : vertices) {
			if (value) penalty(aux, v, Wide(profit));
			else penalty(v, aux, Wide(profit));
		}
	}
	void add_any_cost(const std::vector<int> &vertices, bool value, Cost cost) {
		assert(cost >= 0);
		add_all_profit(vertices, !value, cost);
		constant_ += Wide(cost);
	}
	void force(int v, bool value) {
		vertex(v);
		value = value != orientation(v);
		hard_.emplace_back(value ? -1 : v, value ? v : -2);
	}
	void forbid(int u, int v, bool u_value, bool v_value) {
		vertex(u), vertex(v);
		if (u == v) {
			if (u_value == v_value) force(u, !u_value);
			return;
		}
		u_value = u_value != orientation(u), v_value = v_value != orientation(v);
		assert(u_value != v_value);
		hard_.emplace_back(u_value ? u : v, u_value ? v : u);
	}
	void imply(int u, int v) { forbid(u, v, true, false); }
	void imply(int u, int v, bool u_value, bool v_value) { forbid(u, v, u_value, !v_value); }
	void same(int u, int v) { imply(u, v); imply(v, u); }
	void different(int u, int v) { forbid(u, v, false, false); forbid(u, v, true, true); }
	void at_most_one(int u, int v) { forbid(u, v, true, true); }
	void at_least_one(int u, int v) { forbid(u, v, false, false); }
	std::optional<Result> solve() const {
		Wide bound = 0, base = constant_;
		std::size_t count = edges_.size() + hard_.size();
		for (const auto &edge : edges_) bound += Wide(edge.cost);
		for (Wide cost : unary_) {
			bound += cost < 0 ? -cost : cost;
			count += cost != 0;
			if (cost < 0) base += cost;
		}
		assert(bound < Wide(std::numeric_limits<Cap>::max()));
		const Cap infinity = capacity(bound + 1);
		const int source = static_cast<int>(unary_.size()), sink = source + 1;
		MaxFlow<Cap> graph(source + 2);
		graph.reserve(count);
		auto endpoint = [&](int v) { return v == -1 ? source : v == -2 ? sink : v; };
		for (auto [u, v] : hard_) graph.add_edge(endpoint(u), endpoint(v), infinity);
		if (!hard_.empty() && graph.min_cut(source)[sink]) return std::nullopt;
		for (const auto &edge : edges_) graph.add_edge(edge.from, edge.to, edge.cost);
		for (int v = 0; v < source; ++v) {
			if (unary_[v] < 0) graph.add_edge(source, v, capacity(-unary_[v]));
			else if (unary_[v] > 0) graph.add_edge(v, sink, capacity(unary_[v]));
		}
		Wide cost = base + Wide(graph.flow(source, sink));
		auto selected = graph.min_cut(source);
		selected.resize(n_);
		if (!flipped_.empty()) for (int v = 0; v < n_; ++v) selected[v] = selected[v] != flipped_[v];
		return Result{cost, std::move(selected)};
	}
};

#endif

#line 1 "graph/project_selection.hpp"



#line 1 "graph/max_flow.hpp"



#line 1 "components/flow_graph.hpp"



#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

namespace flow_detail {
template<class Cap> struct Graph {
	struct Arc { int to; Cap cap; };
	int n;
	std::vector<Arc> arcs;
	std::vector<int> start, order;
	bool built = false;
	explicit Graph(int n = 0) : n(n) { assert(n >= 0); }
	void reserve(std::size_t m) { assert(m <= std::size_t(std::numeric_limits<int>::max() / 2)); arcs.reserve(2 * m); }
	int add_edge(int from, int to, Cap cap) {
		assert(0 <= from && from < n && 0 <= to && to < n && cap >= 0);
		assert(arcs.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
		int id = int(arcs.size());
		arcs.push_back({to, cap});
		arcs.push_back({from, Cap(0)});
		built = false;
		return id / 2;
	}
	void build() {
		if (built) return;
		start.assign(std::size_t(n) + 1, 0);
		for (std::size_t i = 0; i < arcs.size(); ++i) ++start[arcs[i ^ 1].to + 1];
		for (int v = 0; v < n; ++v) start[v + 1] += start[v];
		order.resize(arcs.size());
		auto next = start;
		for (int i = 0; i < int(arcs.size()); ++i) order[next[arcs[i ^ 1].to]++] = i;
		built = true;
	}
	void reset_flow() {
		for (std::size_t i = 0; i < arcs.size(); i += 2) arcs[i].cap += arcs[i + 1].cap, arcs[i + 1].cap = 0;
	}
};
}


#line 1 "components/push_relabel.hpp"



#line 5 "components/push_relabel.hpp"
#include <cstdint>

namespace flow_detail {
template<class Cap> Cap push_relabel(Graph<Cap>& graph, int s, int t) {
	graph.build();
	int n = graph.n;
	assert(n <= std::numeric_limits<int>::max() / 2 - 1);
	int dead = 2 * n;
	std::vector<__uint128_t> excess(n);
	std::vector<int> height(n), current(n), count(std::size_t(dead) + 1), head(std::size_t(dead) + 1, -1), next(n), queue(n);
	std::vector<unsigned char> active(n);
	int highest = -1;
	std::size_t work = 0, threshold = std::max<std::size_t>(1, 4 * graph.arcs.size() + n);
	auto activate = [&](int v) {
		if (v == s || v == t || active[v] || !excess[v] || height[v] == dead) return;
		active[v] = 1;
		next[v] = head[height[v]], head[height[v]] = v;
		highest = std::max(highest, height[v]);
	};
	auto buckets = [&] {
		std::fill(head.begin(), head.end(), -1);
		std::fill(active.begin(), active.end(), 0);
		highest = -1;
		for (int v = 0; v < n; ++v) activate(v);
	};
	auto global = [&] {
		std::fill(height.begin(), height.end(), n + 1);
		std::fill(count.begin(), count.end(), 0);
		std::copy_n(graph.start.begin(), n, current.begin());
		height[s] = n, height[t] = 0;
		int first = 0, last = 0;
		queue[last++] = t;
		while (first < last) {
			int v = queue[first++];
			for (int j = graph.start[v]; j < graph.start[v + 1]; ++j) {
				int i = graph.order[j], u = graph.arcs[i].to;
				if (u != s && height[u] == n + 1 && graph.arcs[i ^ 1].cap) height[u] = height[v] + 1, queue[last++] = u;
			}
		}
		for (int h : height) ++count[h];
		buckets();
		work = 0;
	};
	for (int j = graph.start[s]; j < graph.start[s + 1]; ++j) {
		int i = graph.order[j];
		auto& e = graph.arcs[i];
		if (e.to == s || !e.cap) continue;
		excess[e.to] += e.cap, graph.arcs[i ^ 1].cap += e.cap, e.cap = 0;
	}
	global();
	while (highest >= 0) {
		if (head[highest] < 0) { --highest; continue; }
		int v = head[highest];
		head[highest] = next[v];
		if (!active[v] || height[v] != highest) continue;
		active[v] = 0;
		while (excess[v] && height[v] < dead) {
			if (current[v] == graph.start[v + 1]) {
				int old = height[v], value = dead;
				for (int j = graph.start[v]; j < graph.start[v + 1]; ++j) {
					const auto& e = graph.arcs[graph.order[j]];
					if (e.cap) value = std::min(value, height[e.to] + 1);
				}
				work += graph.start[v + 1] - graph.start[v];
				--count[old], ++count[value], height[v] = value, current[v] = graph.start[v];
				if (old < n && !count[old]) {
					for (int u = 0; u < n; ++u) if (old < height[u] && height[u] < n) {
						--count[height[u]], height[u] = n + 1, ++count[n + 1], current[u] = graph.start[u];
					}
					buckets();
					break;
				}
			} else {
				++work;
				int i = graph.order[current[v]];
				auto& e = graph.arcs[i];
				if (!e.cap || height[v] != height[e.to] + 1) { ++current[v]; continue; }
				Cap amount = Cap(std::min(excess[v], __uint128_t(e.cap)));
				e.cap -= amount, graph.arcs[i ^ 1].cap += amount;
				excess[v] -= amount, excess[e.to] += amount;
				activate(e.to);
			}
		}
		activate(v);
		if (work >= threshold) global();
	}
	assert(excess[t] <= __uint128_t(std::numeric_limits<Cap>::max()));
	return Cap(excess[t]);
}
}


#line 7 "graph/max_flow.hpp"
#include <type_traits>

template<class Cap = std::int64_t> class MaxFlow {
	static_assert(std::is_integral_v<Cap> && !std::is_same_v<Cap, bool> && sizeof(Cap) <= 8);
	flow_detail::Graph<Cap> graph_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < graph_.n); }
	int index(int i) const { assert(0 <= i && std::size_t(i) < graph_.arcs.size() / 2); return 2 * i; }

  public:
	struct Edge { int from, to; Cap cap, flow; };
	explicit MaxFlow(int n = 0) : graph_(n) {}
	int size() const { return graph_.n; }
	int edge_count() const { return int(graph_.arcs.size() / 2); }
	void reserve(std::size_t m) { graph_.reserve(m); }
	int add_edge(int from, int to, Cap cap) { return graph_.add_edge(from, to, cap); }
	Edge get_edge(int i) const {
		int j = index(i);
		const auto& a = graph_.arcs[j];
		const auto& b = graph_.arcs[j ^ 1];
		return {b.to, a.to, Cap(a.cap + b.cap), b.cap};
	}
	std::vector<Edge> edges() const {
		std::vector<Edge> result;
		result.reserve(edge_count());
		for (int i = 0; i < edge_count(); ++i) result.push_back(get_edge(i));
		return result;
	}
	void change_edge(int i, Cap cap, Cap flow) {
		assert(0 <= flow && flow <= cap);
		int j = index(i);
		graph_.arcs[j].cap = cap - flow, graph_.arcs[j ^ 1].cap = flow;
	}
	void reset_flow() { graph_.reset_flow(); }
	Cap flow(int s, int t) {
		vertex(s), vertex(t);
		assert(s != t);
		return flow_detail::push_relabel(graph_, s, t);
	}
	Cap flow(int s, int t, Cap limit) {
		vertex(s), vertex(t);
		assert(s != t && limit >= 0);
		graph_.build();
		auto& g = graph_;
		std::vector<int> level(g.n), iter(g.n), queue(g.n);
		struct Frame { int v; Cap limit, sent; };
		std::vector<Frame> stack;
		stack.reserve(g.n);
		Cap total = 0;
		while (total < limit) {
			std::fill(level.begin(), level.end(), -1);
			level[s] = 0;
			int head = 0, tail = 0;
			queue[tail++] = s;
			while (head < tail && level[t] < 0) {
				int v = queue[head++];
				for (int i = g.start[v]; i < g.start[v + 1]; ++i) {
					const auto& e = g.arcs[g.order[i]];
					if (!e.cap || level[e.to] >= 0) continue;
					level[e.to] = level[v] + 1;
					queue[tail++] = e.to;
				}
			}
			if (level[t] < 0) break;
			std::copy_n(g.start.begin(), g.n, iter.begin());
			stack.push_back({t, Cap(limit - total), Cap(0)});
			while (!stack.empty()) {
				auto& frame = stack.back();
				int v = frame.v;
				if (v == s || frame.sent == frame.limit || iter[v] == g.start[v + 1]) {
					Cap sent = v == s ? frame.limit : frame.sent;
					if (v != s && sent < frame.limit) level[v] = g.n;
					stack.pop_back();
					if (stack.empty()) { total += sent; break; }
					auto& parent = stack.back();
					int id = g.order[iter[parent.v]];
					g.arcs[id].cap += sent, g.arcs[id ^ 1].cap -= sent;
					parent.sent += sent;
					if (parent.sent < parent.limit) ++iter[parent.v];
				} else {
					int id = g.order[iter[v]];
					const auto& e = g.arcs[id];
					if (level[e.to] < 0 || level[e.to] >= level[v] || !g.arcs[id ^ 1].cap) ++iter[v];
					else stack.push_back({e.to, std::min<Cap>(frame.limit - frame.sent, g.arcs[id ^ 1].cap), Cap(0)});
				}
			}
		}
		return total;
	}
	std::vector<bool> min_cut(int s) {
		vertex(s);
		graph_.build();
		std::vector<bool> visited(graph_.n);
		std::vector<int> queue{ s };
		visited[s] = true;
		for (std::size_t head = 0; head < queue.size(); ++head) {
			int v = queue[head];
			for (int i = graph_.start[v]; i < graph_.start[v + 1]; ++i) {
				const auto& e = graph_.arcs[graph_.order[i]];
				if (e.cap && !visited[e.to]) visited[e.to] = true, queue.push_back(e.to);
			}
		}
		return visited;
	}
};


#line 5 "graph/project_selection.hpp"
#include <array>
#line 10 "graph/project_selection.hpp"
#include <optional>
#line 12 "graph/project_selection.hpp"
#include <utility>
#line 14 "graph/project_selection.hpp"

template<class Cost = std::int64_t> class ProjectSelection {
	static_assert(std::is_integral_v<Cost> && std::is_signed_v<Cost> && sizeof(Cost) <= 8);
	using Wide = __int128_t;
	using Cap = std::uint64_t;
	struct Edge { int from, to; Cap cost; };
	int n_;
	Wide constant_ = 0;
	std::vector<Wide> unary_;
	std::vector<bool> flipped_;
	std::vector<Edge> edges_;
	std::vector<std::pair<int, int>> hard_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < n_); }
	bool orientation(int v) const { return !flipped_.empty() && flipped_[v]; }
	void unary(int v, Wide c0, Wide c1) {
		vertex(v);
		if (orientation(v)) std::swap(c0, c1);
		constant_ += c0;
		unary_[v] += c1 - c0;
	}
	static Cap capacity(Wide cost) {
		assert(0 <= cost && cost <= std::numeric_limits<Cap>::max());
		return static_cast<Cap>(cost);
	}
	void penalty(int from, int to, Wide cost) {
		assert(cost >= 0);
		if (cost && from != to) edges_.push_back({from, to, capacity(cost)});
	}
	void pair(int u, int v, std::array<Wide, 4> cost) {
		vertex(u), vertex(v);
		if (u == v) { unary(u, cost[0], cost[3]); return; }
		if (orientation(u)) std::swap(cost[0], cost[2]), std::swap(cost[1], cost[3]);
		if (orientation(v)) std::swap(cost[0], cost[1]), std::swap(cost[2], cost[3]);
		Wide delta = cost[1] + cost[2] - cost[0] - cost[3];
		assert(delta >= 0);
		constant_ += cost[0];
		unary_[u] += cost[3] - cost[1];
		unary_[v] += cost[1] - cost[0];
		penalty(u, v, delta);
	}
	void condition(int u, int v, bool u_value, bool v_value, Wide cost) {
		vertex(u), vertex(v);
		if (u == v) {
			if (u_value == v_value) unary(u, u_value ? 0 : cost, u_value ? cost : 0);
			return;
		}
		if (cost >= 0) {
			u_value = u_value != orientation(u), v_value = v_value != orientation(v);
			assert(!cost || u_value != v_value);
			penalty(u_value ? u : v, u_value ? v : u, cost);
			return;
		}
		std::array<Wide, 4> table{};
		table[2 * int(u_value) + int(v_value)] = cost;
		pair(u, v, table);
	}
	int auxiliary() {
		assert(unary_.size() < std::size_t(std::numeric_limits<int>::max() / 2 - 3));
		int v = static_cast<int>(unary_.size());
		unary_.push_back(0);
		return v;
	}

  public:
	using cost_type = Cost;
	using total_type = Wide;
	struct Result {
		Wide cost;
		std::vector<bool> selected;
		Wide profit() const { return -cost; }
	};
	explicit ProjectSelection(int n = 0) : n_(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2 - 3);
		unary_.resize(n);
	}
	ProjectSelection(int n, const std::vector<bool> &flipped) : ProjectSelection(n) {
		assert(flipped.size() == std::size_t(n));
		flipped_ = flipped;
	}
	int size() const { return n_; }
	bool is_flipped(int v) const { vertex(v); return orientation(v); }
	void add_constant(Cost cost) { constant_ += Wide(cost); }
	void add_cost(int v, Cost cost) { unary(v, 0, Wide(cost)); }
	void add_cost(int v, Cost false_cost, Cost true_cost) { unary(v, Wide(false_cost), Wide(true_cost)); }
	void add_profit(int v, Cost profit) { unary(v, 0, -Wide(profit)); }
	void add_profit(int v, Cost false_profit, Cost true_profit) { unary(v, -Wide(false_profit), -Wide(true_profit)); }
	void add_cost_if(int v, bool value, Cost cost) { unary(v, value ? 0 : Wide(cost), value ? Wide(cost) : 0); }
	void add_profit_if(int v, bool value, Cost profit) { unary(v, value ? 0 : -Wide(profit), value ? -Wide(profit) : 0); }
	void add_cost_if(int u, int v, bool u_value, bool v_value, Cost cost) {
		condition(u, v, u_value, v_value, Wide(cost));
	}
	void add_profit_if(int u, int v, bool u_value, bool v_value, Cost profit) {
		condition(u, v, u_value, v_value, -Wide(profit));
	}
	void add_penalty(int u, int v, Cost cost) {
		assert(cost >= 0);
		add_cost_if(u, v, true, false, cost);
	}
	void add_difference_cost(int u, int v, Cost cost) {
		vertex(u), vertex(v);
		assert(cost >= 0 && (u == v || !cost || orientation(u) == orientation(v)));
		penalty(u, v, Wide(cost));
		penalty(v, u, Wide(cost));
	}
	void add_same_cost(int u, int v, Cost cost) {
		vertex(u), vertex(v);
		assert(cost >= 0);
		if (u == v) { constant_ += Wide(cost); return; }
		assert(!cost || orientation(u) != orientation(v));
		penalty(u, v, Wide(cost));
		penalty(v, u, Wide(cost));
	}
	void add_same_profit(int u, int v, Cost profit) {
		assert(profit >= 0);
		add_difference_cost(u, v, profit);
		constant_ -= Wide(profit);
	}
	void add_difference_profit(int u, int v, Cost profit) {
		assert(profit >= 0);
		add_same_cost(u, v, profit);
		constant_ -= Wide(profit);
	}
	void add_pair_cost(int u, int v, Cost c00, Cost c01, Cost c10, Cost c11) {
		pair(u, v, {Wide(c00), Wide(c01), Wide(c10), Wide(c11)});
	}
	void add_pair_profit(int u, int v, Cost p00, Cost p01, Cost p10, Cost p11) {
		pair(u, v, {-Wide(p00), -Wide(p01), -Wide(p10), -Wide(p11)});
	}
	void add_all_profit(const std::vector<int> &vertices, bool value, Cost profit) {
		assert(profit >= 0);
		for ([[maybe_unused]] int v : vertices) vertex(v);
		if (!profit) return;
		if (vertices.empty()) { constant_ -= Wide(profit); return; }
		if (vertices.size() == 1) {
			add_profit_if(vertices[0], value, profit);
			return;
		}
		for ([[maybe_unused]] int v : vertices) assert(orientation(v) == orientation(vertices[0]));
		value = value != orientation(vertices[0]);
		int aux = auxiliary();
		if (value) unary_[aux] -= Wide(profit);
		else constant_ -= Wide(profit), unary_[aux] += Wide(profit);
		for (int v : vertices) {
			if (value) penalty(aux, v, Wide(profit));
			else penalty(v, aux, Wide(profit));
		}
	}
	void add_any_cost(const std::vector<int> &vertices, bool value, Cost cost) {
		assert(cost >= 0);
		add_all_profit(vertices, !value, cost);
		constant_ += Wide(cost);
	}
	void force(int v, bool value) {
		vertex(v);
		value = value != orientation(v);
		hard_.emplace_back(value ? -1 : v, value ? v : -2);
	}
	void forbid(int u, int v, bool u_value, bool v_value) {
		vertex(u), vertex(v);
		if (u == v) {
			if (u_value == v_value) force(u, !u_value);
			return;
		}
		u_value = u_value != orientation(u), v_value = v_value != orientation(v);
		assert(u_value != v_value);
		hard_.emplace_back(u_value ? u : v, u_value ? v : u);
	}
	void imply(int u, int v) { forbid(u, v, true, false); }
	void imply(int u, int v, bool u_value, bool v_value) { forbid(u, v, u_value, !v_value); }
	void same(int u, int v) { imply(u, v); imply(v, u); }
	void different(int u, int v) { forbid(u, v, false, false); forbid(u, v, true, true); }
	void at_most_one(int u, int v) { forbid(u, v, true, true); }
	void at_least_one(int u, int v) { forbid(u, v, false, false); }
	std::optional<Result> solve() const {
		Wide bound = 0, base = constant_;
		std::size_t count = edges_.size() + hard_.size();
		for (const auto &edge : edges_) bound += Wide(edge.cost);
		for (Wide cost : unary_) {
			bound += cost < 0 ? -cost : cost;
			count += cost != 0;
			if (cost < 0) base += cost;
		}
		assert(bound < Wide(std::numeric_limits<Cap>::max()));
		const Cap infinity = capacity(bound + 1);
		const int source = static_cast<int>(unary_.size()), sink = source + 1;
		MaxFlow<Cap> graph(source + 2);
		graph.reserve(count);
		auto endpoint = [&](int v) { return v == -1 ? source : v == -2 ? sink : v; };
		for (auto [u, v] : hard_) graph.add_edge(endpoint(u), endpoint(v), infinity);
		if (!hard_.empty() && graph.min_cut(source)[sink]) return std::nullopt;
		for (const auto &edge : edges_) graph.add_edge(edge.from, edge.to, edge.cost);
		for (int v = 0; v < source; ++v) {
			if (unary_[v] < 0) graph.add_edge(source, v, capacity(-unary_[v]));
			else if (unary_[v] > 0) graph.add_edge(v, sink, capacity(unary_[v]));
		}
		Wide cost = base + Wide(graph.flow(source, sink));
		auto selected = graph.min_cut(source);
		selected.resize(n_);
		if (!flipped_.empty()) for (int v = 0; v < n_; ++v) selected[v] = selected[v] != flipped_[v];
		return Result{cost, std::move(selected)};
	}
};