n, m = read_line.split.map(&.to_i) total = m.to_i64 * n src = n snk = n + 1 f = Dinic.new(n + 2) n.times do |i| k, c = read_line.split.map(&.to_i) f.add_edge(i, snk, c.to_i64) if k > 0 a = read_line.split.map(&.to_i) b = read_line.split.map(&.to_i64) total += b.sum f.add_edge(src, i, b.sum + m) k.times do |j| f.add_edge(i, a[j] - 1, b[j]) end end end puts total - f.calc(src, snk) # adjacent list class Dinic class Edge property :to, :cap, :rev def initialize(@to : Int32, @cap : Int64, @rev : Int32) end end getter :g @g : Array(Array(Edge)) @level : Array(Int32) @next : Array(Int32) def initialize(size : Int32) @g = Array.new(size) { Array(Edge).new } @level = Array.new(size, -1) @next = Array.new(size, 0) end def add_edge(s : Int32, t : Int32, cap : Int64) @g[s] << Edge.new(t, cap, @g[t].size) @g[t] << Edge.new(s, 0i64, @g[s].size - 1) end private def bfs(s) @level.fill(-1) @level[s] = 0 que = [s] @g.size.times do |i| break if i == que.size cur = que[i] @g[cur].each do |edge| if edge.cap > 0 && @level[edge.to] == -1 @level[edge.to] = @level[cur] + 1 que << edge.to end end end end private def dfs(pos : Int32, t : Int32, f : Int64) return f if pos == t while @next[pos] < @g[pos].size e = @g[pos][@next[pos]] if e.cap > 0 && @level[pos] < @level[e.to] v = dfs(e.to, t, {e.cap, f}.min) if v > 0 e.cap -= v @g[e.to][e.rev].cap += v return v end end @next[pos] += 1 end return 0i64 end def calc(s : Int32, t : Int32) : Int64 flow = 0i64 while true bfs(s) if @level[t] == -1 return flow end @next.fill(0) while true f = dfs(s, t, Int64::MAX) break if f <= 0 flow += f end end end end