import sys
# sys.setrecursionlimit(200005)
# sys.set_int_max_str_digits(200005)
int1 = lambda x: int(x)-1
pDB = lambda *x: print(*x, end="\n", file=sys.stderr)
p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr)
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def SI(): return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
# inf = -1-(-1 << 31)
inf = -1-(-1 << 62)
# md = 10**9+7
md = 998244353
from collections import deque
class MaxFlow():
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)]
self.pos = []
def add_edge(self, fr, to, cap):
m = len(self.pos)
self.pos.append((fr, len(self.graph[fr])))
fr_id = len(self.graph[fr])
to_id = len(self.graph[to])
if fr == to: to_id += 1
self.graph[fr].append([to, to_id, cap])
self.graph[to].append([fr, fr_id, 0])
return m
def get_edge(self, idx):
to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
rev_to, rev_rev, rev_cap = self.graph[to][rev]
return rev_to, to, cap + rev_cap, rev_cap
def edges(self):
m = len(self.pos)
for i in range(m):
yield self.get_edge(i)
def dfs(self, s, t, up):
stack = [t]
while stack:
v = stack.pop()
if v == s:
flow = up
for v in stack:
to, rev, cap = self.graph[v][self.iter[v]]
flow = min(flow, self.graph[to][rev][2])
for v in stack:
self.graph[v][self.iter[v]][2] += flow
to, rev, cap = self.graph[v][self.iter[v]]
self.graph[to][rev][2] -= flow
return flow
lv = self.level[v]
for i in range(self.iter[v], len(self.graph[v])):
to, rev, cap = self.graph[v][i]
if lv > self.level[to] and self.graph[to][rev][2]:
self.iter[v] = i
stack.append(v)
stack.append(to)
break
else:
self.iter[v] = len(self.graph[v])
self.level[v] = self.n
return 0
def max_flow(self, s, t):
return self.max_flow_with_limit(s, t, 2**63 - 1)
def max_flow_with_limit(self, s, t, limit):
flow = 0
while flow < limit:
self.level = [-1] * self.n
self.level[s] = 0
queue = deque()
queue.append(s)
while queue:
v = queue.popleft()
for to, rev, cap in self.graph[v]:
if cap == 0 or self.level[to] >= 0: continue
self.level[to] = self.level[v] + 1
if to == t: break
queue.append(to)
if self.level[t] == -1: break
self.iter = [0] * self.n
while flow < limit:
f = self.dfs(s, t, limit - flow)
if not f: break
flow += f
return flow
class CostScalingGraph():
def __init__(self, n):
self.n = n
self.edges = []
self.excess = [0] * n
self.maxcost = 0
self.graph = [[] for _ in range(self.n)]
self.pos = []
self.dual = [0] * n
def add_edge(self, fr, to, lower, upper, cost):
self.maxcost = max(self.maxcost, cost, -cost)
self.edges.append([fr, to, lower, upper, 0, cost])
def add_excess(self, v, x):
self.excess[v] += x
def solve(self):
mf = MaxFlow(self.n + 2)
sv = self.n
tv = self.n + 1
for fr, to, lower, upper, flow, cost in self.edges:
self.excess[to] += lower
self.excess[fr] -= lower
mf.add_edge(fr, to, upper - lower)
excess_s_sum = excess_t_sum = 0
for i in range(self.n):
if self.excess[i] > 0:
excess_s_sum += self.excess[i]
mf.add_edge(sv, i, self.excess[i])
if self.excess[i] < 0:
excess_t_sum -= self.excess[i]
mf.add_edge(i, tv, -self.excess[i])
if excess_s_sum != excess_t_sum or mf.max_flow(sv, tv) != excess_s_sum:
return False, 0
m = len(self.edges)
for i in range(m):
fr, to, cap, flow = mf.get_edge(i)
cost = self.edges[i][5] * (self.n + 1)
fr_id = len(self.graph[fr])
to_id = len(self.graph[to])
if fr == to: to_id += 1
self.pos.append([fr, fr_id])
self.graph[fr].append([to, to_id, cap - flow, cost])
self.graph[to].append([fr, fr_id, flow, -cost])
self.eps = (self.n + 1) * self.maxcost
while self.eps > 1:
self.eps = max(self.eps >> 2, 1)
self.refine()
res = 0
for i in range(m):
fr, _, lower, upper, flow, cost = self.edges[i]
to, rev, cap, _ = self.graph[self.pos[i][0]][self.pos[i][1]]
self.edges[i][4] = upper - cap
res += (upper - cap) * cost
self.dual = [0] * self.n
while True:
update = False
for i in range(self.n):
for to, rev, cap, cost in self.graph[i]:
if cap == 0: continue
cost = self.dual[i] + cost // (self.n + 1)
if cost < self.dual[to]:
self.dual[to] = cost
update = True
if not update: break
return True, res
def refine(self):
excess = [0] * self.n
for u in range(self.n):
for v, e in enumerate(self.graph[u]):
to, rev, cap, cost = e
if cap != 0 and cost + self.dual[u] - self.dual[to] < 0:
excess[u] -= cap
excess[to] += cap
self.graph[to][rev][2] += cap
self.graph[u][v][2] -= cap
actives_on = [False] * self.n
actives = deque()
iter = [0] * self.n
for i in range(self.n):
if excess[i] > 0:
actives.append(i)
actives_on[i] = True
while actives:
u = actives.popleft()
actives_on[u] = False
for i in range(iter[u], len(self.graph[u])):
to, rev, cap, cost = self.graph[u][i]
if cap != 0 and cost + self.dual[u] - self.dual[to] < 0:
cap = min(excess[u], cap)
excess[u] -= cap
excess[to] += cap
self.graph[to][rev][2] += cap
self.graph[u][i][2] -= cap
if not actives_on[to] and excess[to] > 0:
actives_on[to] = True
actives.append(to)
if excess[u] == 0:
iter[u] = i
break
else:
iter[u] = len(self.graph[u])
if excess[u] > 0:
iter[u] = 0
down = (self.n + 1) * self.maxcost
for to, rev, cap, cost in self.graph[u]:
if cap != 0:
down = min(down, self.eps + cost + self.dual[u] - self.dual[to])
self.dual[u] -= down
actives.append(u)
actives_on[u] = True
self.eps = 0
for u in range(self.n):
for to, rev, cap, cost in self.graph[u]:
if cap != 0:
self.eps = max(self.eps, -cost - self.dual[u] + self.dual[to])
mx=10**9
n,k=LI()
mf=CostScalingGraph(n)
aa=[]
for i in range(n):
if i:mf.add_edge(i-1,i,0,n,mx)
a,m=LI()
aa.append(a)
for j in LI1():
if j<i and aa[j]<a:
mf.add_edge(j,i,0,1,mx*(i-j)-a+aa[j])
mf.add_excess(0,k)
mf.add_excess(n-1,-k)
f=mf.solve()
ans = mx*(n-1)*k-f[1]
print(ans)