Giả sử bạn là Lý Hoa.
Là một học sinh ban xã hội ưu tú, gần đây bạn đã học về điện học.
Bạn có $\infty$ các hạt điện tích điểm với điện tích $+e$ và động năng đủ lớn. Bạn cần đưa một phần trong số đó vào một cỗ máy và lấy ra một lượng điện tích tương ứng. Hãy tối đa hóa tổng động năng của các điện tích sau khi cỗ máy hoạt động.
Cỗ máy có thể được coi là một đồ thị gồm $n$ nút, tại nút thứ $i$ có điện thế là $h_i \,\mathrm{V}$.
Tại nút thứ $i$ có $p_i$ đường ống để đưa điện tích vào. Trong suốt quá trình, mỗi đường ống chỉ có thể đưa vào tối đa một điện tích. Khi đưa một điện tích qua đường ống thứ $j$ tại nút $i$, nó phải thực hiện công $a_{i,j} \,\mathrm{eV}$ để thắng ngoại lực.
Tại nút thứ $i$ có $q_i$ đường ống để đưa điện tích ra. Trong suốt quá trình, mỗi đường ống chỉ có thể đưa ra tối đa một điện tích. Khi đưa một điện tích qua đường ống thứ $j$ tại nút $i$, nó phải thực hiện công $b_{i,j} \,\mathrm{eV}$ để thắng ngoại lực.
Bên trong cỗ máy có $m$ đường ống một chiều kết nối các nút. Đường ống thứ $i$ nối từ $u_i$ đến $v_i$, cho phép vận chuyển điện tích từ $u_i$ đến $v_i$ (không giới hạn số lần). Giả sử các lực khác bên trong máy không thực hiện công, và bạn có thể điều khiển quỹ đạo chuyển động của mỗi điện tích thông qua cỗ máy.
Mỗi điện tích được đưa vào phải được đưa ra, và các lực khác bên trong máy không thực hiện công. Nghĩa là, nếu một điện tích đi vào từ đường ống thứ $i$ tại nút $x$ và đi ra từ đường ống thứ $j$ tại nút $y$, công mà máy thực hiện lên nó là $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$.
Hãy tính tổng độ tăng động năng lớn nhất (đơn vị: $\mathrm{eV}$).
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên dương $n, m$.
Dòng tiếp theo chứa $n$ số nguyên, số thứ $i$ là $h_i$.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u_i, v_i$ mô tả một đường ống một chiều.
$n$ dòng tiếp theo, dòng thứ $i$ bắt đầu bằng số nguyên dương $p_i$, theo sau là $p_i$ số nguyên không âm, số thứ $j$ biểu thị $a_{i,j}$.
$n$ dòng tiếp theo, dòng thứ $i$ bắt đầu bằng số nguyên dương $q_i$, theo sau là $q_i$ số nguyên không âm, số thứ $j$ biểu thị $b_{i,j}$.
Dữ liệu ra
In ra một số nguyên không âm là đáp án.
Ví dụ
Dữ liệu vào 1
3 4 3 9 2 1 1 2 3 3 3 3 2 1 2 1 0 1 2 1 1 1 2 1 1
Dữ liệu ra 1
6
Ví dụ 2~5
Xem tệp đính kèm.
Giới hạn
Với $100\%$ dữ liệu, đảm bảo $1 \le u_i, v_i \le n$, $0 \le m, p_i, q_i, a_{i,j}, b_{i,j}, h_i$. Trong đó $a_{i,j}, b_{i,j}, h_i$ được tạo ngẫu nhiên với xác suất đều trong phạm vi tương ứng, các giá trị còn lại được tạo ngẫu nhiên theo một cách nào đó và không nhằm mục đích làm quá tải các thuật toán như SPFA.
| Số hiệu test | $n \le$ | $m \le$ | $p_i, q_i \le$ | $a_{i,j}, b_{i,j} <$ | $h_i <$ | Tính chất đặc biệt |
|---|---|---|---|---|---|---|
| $1, 2$ | $50$ | $200$ | $10$ | $10$ | $30$ | Không |
| $3, 4$ | $300$ | $100$ | $100$ | $2000$ | ||
| $5, 6, 7, 8$ | $100$ | $500$ | $200$ | $200$ | $10^4$ | |
| $9, 10$ | $2000$ | $5000$ | $500$ | $10^4$ | $10^6$ | A |
| $11, 12, 13, 14$ | $n-1$ | B | ||||
| $15, 16, 17, 18$ | $10^4$ | C | ||||
| $19, 20, 21$ | $700$ | $5000$ | $1000$ | $10^6$ | $10^8$ | Không |
| $22, 23, 24, 25$ | $2000$ | $2 \times 10^4$ | $2000$ |
Tính chất đặc biệt A: $|u_i - v_i| = 1$
Tính chất đặc biệt B: $m = n - 1, u_i < v_i, v_i = i + 1$
Tính chất đặc biệt C: $\min \{u_i, v_i\} \le 4$
Tệp đính kèm
Do quy mô dữ liệu vào/ra của bài toán này khá lớn, chúng tôi cung cấp thêm một bộ thư viện I/O.
Tệp nén này bao gồm năm ví dụ và bộ thư viện I/O.