Vì bài này quá KHÓ nên sẽ không nằm trong contest Mathematical Algorithms TWK II Open ∮

Youtuber_TWK xây dưng một hệ thống gồm nhiều mô-đun xử lý độc lập:

• Có \(N\) thiết bị và \(N\) kênh. Chi phí khi thiết bị \(i\) dùng kênh \(j\) là \(C[i][j]\). Mỗi thiết bị và mỗi kênh xuất hiện đúng một lần trong phép ghép. Gọi tổng chi phí nhỏ nhất là \(H\).

• Một mạng hai phía có \(P\) đỉnh trái, \(Q\) đỉnh phải và \(E\) cạnh. Mỗi đỉnh chỉ được dùng trong nhiều nhất một cạnh được chọn. Gọi số cạnh lớn nhất có thể chọn là \(K\).

• Có \(V\) công tắc nhị phân. Mỗi ràng buộc có dạng \((a\lor b)\). Literal dương \(k\) đúng khi công tắc \(k\) bật, literal âm \(-k\) đúng khi công tắc \(k\) tắt. Trong các cấu hình thỏa mãn tất cả ràng buộc, chọn cấu hình theo thứ tự ưu tiên từ điển trên vector trạng thái \((x_1,x_2,\ldots,x_V)\), với \(0<1\). Gọi số công tắc bật trong cấu hình được chọn là \(B\). Nếu không có cấu hình hợp lệ, in \(-1\).

• Cho hai dãy \(P,Q\) độ dài \(d+1\). Tìm \(R\) thỏa mãn \(P=Q*R\pmod {998244353}\) và lấy \(R[d]\).

• Có \(S\) bit và mảng \(F\) gồm \(2^S\) phần tử. Với mask \(M\), đặt \(Z\) bằng tổng \(F[X]\) trên mọi \(X\) thỏa mãn \(X\&M=X\).

• Có \(W\) trọng lượng \(w[i]\) và giới hạn \(L\). Chọn một tập bất kỳ sao cho tổng trọng lượng không vượt quá \(L\). Gọi tổng lớn nhất đạt được là \(S_w\).

• Với hai dãy \(A,B\), tại mỗi \(t\) xét các cặp \(i,j\) thỏa mãn \(0\le i<NA,\ 0\le j<NB,\ i+j=t\). Gọi giá trị nhỏ nhất và lớn nhất của \(A[i]+B[j]\) lần lượt là \(mn[t]\) và \(mx[t]\). Đặt \(Lmin=\sum_tmn[t]\) và \(Lmax=\sum_tmx[t]\).

• Có \(R\) điểm \((x[i],y[i],z[i])\). Đếm số cặp chỉ số \(i<j\) thỏa mãn \(x[i]\le x[j],\ y[i]\le y[j],\ z[i]\le z[j]\). Gọi số cặp đó là \(T\).

\(\qquad\) Đưa ra đáp án của \(\ H+2(P+Q-K)+B+R[d]+Z+S_w+Lmin+Lmax+T.\)

Input

• Dòng đầu chứa \(N\).

• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) giá trị \(C[i][j]\).

• Dòng tiếp theo chứa \(P,Q,E\), sau đó là \(E\) cạnh \(u,v\).

• Dòng tiếp theo chứa \(V,Cc\), sau đó là \(Cc\) ràng buộc \(a,b\).

• Dòng tiếp theo chứa \(d\), sau đó là hai dãy \(P[0..d]\) và \(Q[0..d]\).

• Dòng tiếp theo chứa \(S,M\), sau đó là \(2^S\) giá trị \(F\).

• Dòng tiếp theo chứa \(W,L\), sau đó là \(W\) trọng lượng \(w[i]\).

• Dòng tiếp theo chứa \(NA,NB\), sau đó lần lượt là \(NA\) giá trị của \(A\) và \(NB\) giá trị của \(B\).

• Dòng tiếp theo chứa \(R\), sau đó là \(R\) bộ \(x[i],y[i],z[i]\).

Output

Nếu hệ công tắc không có cấu hình hợp lệ, in \(-1\).

Ngược lại, in \(H+2(P+Q-K)+B+R[d]+Z+S_w+Lmin+Lmax+T.\)

Constraints

• \(1 \le N \le 80\)
• \(1 \le P,Q,V,Cc,S,W,NA,NB \le 10^4\)
• \(0 \le E,L,x[i],y[i],z[i] \le 10^{14}\)
• \(1 \le d,R \le 2 \cdot 10^5\)
• Các hệ số của \(P,Q\) thuộc \([0,998244352]\).
• \(Q[0]\ne0\).
• Đáp án nằm trong signed long long.

Example

1
7
1 2 1
1 1
1 1
1 1
1
2 3
1 1
2 2 2
1 2 3 4
2 5
2 4
2 2
1 5
2 3
3
1 1 1
1 2 2
2 2 2

48

3
4 2 7
3 6 1
5 4 2
3 3 4
1 1
1 2
2 2
3 3
3 3
1 2
-1 3
2 3
2
1 3 3
1 1 0
2 3
1 2 3 4
3 8
3 4 6
3 4
1 5 2
4 2 6 3
4
2 7 1 5
3 1 4 2
2 2 2
3 3 3
4 1 5

108

Scoring

• Subtask 1 (5%): \(N\le 6\), \(P,Q\le 80\), \(V\le 80\), \(d\le 5000\), \(S\le 6\), \(W\le 12\), \(NA,NB\le 20\), \(R\le 5000\).
• Subtask 2 (5%): \(N\le 18\), \(P,Q\le 240\), \(V\le 240\), \(d\le 15000\), \(S\le 12\), \(W\le 22\), \(NA,NB\le 60\), \(R\le 15000\).
• Subtask 3 (10%): \(N\le 30\), \(P,Q\le 400\), \(V\le 400\), \(d\le 25000\), \(S\le 12\), \(W\le 30\), \(NA,NB\le 100\), \(R\le 25000\).
• Subtask 4 (15%): \(N\le 48\), \(P,Q\le 640\), \(V\le 640\), \(d\le 40000\), \(S\le 16\), \(W\le 30\), \(NA,NB\le 160\), \(R\le 40000\).
• Subtask 5 (65%): \(N\le 80\), \(P,Q\le 1500\), \(E\le 10000\), \(V\le 3000\), \(Cc\le 10000\), \(d\le 200000\), \(S\le 20\), \(W\le 42\), \(L\le 10^{14}\), \(NA,NB\le 300\), \(R\le 200000\).