using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m) = (c[0], c[1]); var pairs = new Pair[n]; for (var i = 0; i < n; ++i) { c = NList; var (k, ci) = (c[0], c[1]); var a = new int[0]; var b = new int[0]; if (k > 0) { a = NList; b = NList; } pairs[i] = new Pair(k, ci, a, b); } WriteLine(Work(n, m, pairs)); } static long Work(int n, int m, Pair[] pairs) { var map = new long[n][]; for (var i = 0; i < map.Length; ++i) map[i] = new long[n]; for (var i = 0; i < n; ++i) { for (var j = 0; j < pairs[i].K; ++j) { var p = Math.Min(i, pairs[i].A[j] - 1); var q = Math.Max(i, pairs[i].A[j] - 1); map[p][q] += pairs[i].B[j]; } } var count = 0; for (var i = 0; i < n; ++i) for (var j = i + 1; j < n; ++j) if (map[i][j] > 0) ++count; var g = new MaxFlowGraph(n + count + 2); var s = n; var t = n + 1; var offset = 0L; for (var i = 0; i < n; ++i) { if (pairs[i].C >= m) { g.AddEdge(s, i, 0); g.AddEdge(i, t, pairs[i].C - m); } else { offset += m - pairs[i].C; g.AddEdge(s, i, m - pairs[i].C); g.AddEdge(i, t, 0); } } var INF = long.MaxValue / 1000; var cur = 0; for (var i = 0; i < n; ++i) for (var j = i + 1; j < n; ++j) if (map[i][j] > 0) { ++cur; g.AddEdge(s, t + cur, map[i][j]); g.AddEdge(t + cur, t, 0); g.AddEdge(t + cur, i, INF); g.AddEdge(t + cur, j, INF); offset += map[i][j]; } var f = g.Flow(s, t); var w = 0L; for (var j = 0; j < n * 2; j += 2) if (g.GetEdge(j).flow > 0) ++w; return w * m + offset - f; } class Pair { public int K; public int C; public int[] A; public int[] B; public Pair(int k, int c, int[] a, int[] b) { K = k; C = c; A = a; B = b; } } static void YN(bool b) { WriteLine(b ? "Yes" : "No"); } // 最大フローグラフ // MaxFlowGraph(n) n:頂点数 // AddEdge(from, to, cap) from,to:0-indexed cap:最大用量 // Flow(from, to) 最大流量を求める 各辺の流量を変更 // Flow(from, to, flowLimit) // MinCut(from) Flow(最小カット)実行後の残余グラフで各頂点への到達可能性を取得 // GetEdge(i), GetEdges() 内部の辺の状態を取得 // ChangeEdge(i, newCap, newFlow) 対象辺の流量を変更 class MaxFlowGraph { int _n; long max = long.MaxValue; class EdgeI { public int to { get; private set; } public int rev { get; private set; } public long cap { get; set; } public EdgeI(int to, int rev, long cap) { this.to = to; this.rev = rev; this.cap = cap; } } List> pos = new List>(); List[] g; public MaxFlowGraph(int n) { _n = n; g = new List[n]; for (var i = 0; i < n; ++i) g[i] = new List(); } public int AddEdge(int from, int to, long cap) { var m = pos.Count; pos.Add(new KeyValuePair(from, g[from].Count)); g[from].Add(new EdgeI(to, g[to].Count, cap)); g[to].Add(new EdgeI(from, g[from].Count - 1, 0)); return m; } public class Edge { public int from { get; private set; } public int to { get; private set; } public long cap { get; private set; } public long flow { get; private set; } public Edge(int from, int to, long cap, long flow) { this.from = from; this.to = to; this.cap = cap; this.flow = flow; } } public Edge GetEdge(int i) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; return new Edge(pos[i].Key, e.to, e.cap + re.cap, re.cap); } public List GetEdges() { var m = pos.Count; var result = new List(); for (var i = 0; i < m; ++i) result.Add(GetEdge(i)); return result; } public void ChangeEdge(int i, long new_cap, long new_flow) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; e.cap = new_cap - new_flow; re.cap = new_flow; } public long Flow(int s, int t) { return Flow(s, t, max); } public long Flow(int s, int t, long limit) { var level = new int[_n]; var iter = new int[_n]; var que = new Queue(); void bfs() { for (var i = 0; i < _n; ++i) level[i] = -1; level[s] = 0; que.Clear(); que.Enqueue(s); while (que.Count > 0) { var v = que.Dequeue(); foreach (var e in g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.Enqueue(e.to); } } } long dfs(int v, long up) { if (v == s) return up; long res = 0; var level_v = level[v]; for (var i = iter[v]; i < g[v].Count; ++i) { var e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; long d = dfs(e.to, Min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) break; } return res; } long flow = 0; while (flow < limit) { bfs(); if (level[t] == -1) break; for (var i = 0; i < iter.Length; ++i) iter[i] = 0; while (flow < limit) { var f = dfs(t, limit - flow); if (f == 0) break; flow += f; } } return flow; } long Min(long a, long b) { return a.CompareTo(b) < 0 ? a : b; } public bool[] MinCut(int s) { var visited = new bool[_n]; var que = new Queue(); que.Enqueue(s); while (que.Count > 0) { var p = que.Dequeue(); visited[p] = true; foreach (var e in g[p]) { if (e.cap != 0 && !visited[e.to]) { visited[e.to] = true; que.Enqueue(e.to); } } } return visited; } } }