CodeEff/ECCO huggingface dataset:
# Original solution
from heapq import heappush as push
from heapq import heappop as pop
def solve():
  n, k = list(map(int,input().split()))
  group_num = 10
  
  book_map = [[] for i in range(group_num)]
  acc_map = [[0] for i in range(group_num)]

  for i in range(n):
    c,g = list(map(int,input().split()))
    push(book_map[g - 1], -c)

  for i in range(group_num):
    bmi = book_map[i]
    append = acc_map[i].append
    acc = 0
    for j in range(len(bmi)):
      acc += (pop(bmi) - j * 2)
      append(acc)
  
  dp = [[0] * (k + 1) for i in range(group_num + 1)]
  for y in range(1,k + 1):
    for x in range(1,group_num + 1):
      mp = acc_map[x - 1]
      be = dp[x - 1]
      for z in range(min(y + 1, len(mp))):
        v1 = be[y - z]
        v2 = mp[z]
        if dp[x][y] > v1 + v2:
          dp[x][y] = v1 + v2
  
  print((-dp[group_num][k]))
solve()



# Optimized solution
def solve():
  n, k = list(map(int,input().split()))
  group_num = 10
  
  book_map = [[] for i in range(group_num)]
  acc_map = [[0] for i in range(group_num)]

  for i in range(n):
    c,g = list(map(int,input().split()))
    book_map[g - 1].append(c)

  for i in range(group_num):
    bmi = book_map[i]
    bmi.sort(reverse=True)
    append = acc_map[i].append
    acc = 0
    for j in range(len(bmi)):
      acc += (bmi[j] + j * 2)
      append(acc)
  
  dp = [[0] * (k + 1) for i in range(group_num + 1)]
  for y in range(1,k + 1):
    for x in range(1,group_num + 1):
      mp = acc_map[x - 1]
      be = dp[x - 1]
      dp[x][y] = max([be[y - z] + mp[z] for z in range(min(y + 1, len(mp)))])
  
  print((dp[group_num][k]))
solve()
# Original solution
# Acceptance of input
import sys

file_input = sys.stdin

V, E = list(map(int, file_input.readline().split()))

D = [[] for i in range(V)]

for line in file_input:
    s, t, d = list(map(int, line.split()))
    D[s].append((t, d))

max_d = 15001

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        if D[v]:
            t, d = min(D[v])
            if t == 0:
                return d
            else:
                return max_d
        else:
            return max_d
    res = max_d
    for t, d in D[v]:
        if b & (1 << t):
            continue
        res = min(res, d + tsp(t, b | (1 << t)))
    return res

# Output
ans = tsp(0, 1)

if ans == max_d:
    print((-1))
else:
    print(ans)

# Optimized solution
max_d = 15001

# Acceptance of input
import sys

file_input = sys.stdin

V, E = list(map(int, file_input.readline().split()))

D = [[max_d] * V for i in range(V)]

for line in file_input:
    s, t, d = list(map(int, line.split()))
    D[s][t] = d

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return D[v][0]
    
    res = max_d
    for t, d in enumerate(D[v]):
        if b & (1 << t) or d == max_d:
            continue
        res = min(res, d + tsp(t, b | (1 << t)))
        
    return res

# Output
ans = tsp(0, 1)

if ans == max_d:
    print((-1))
else:
    print(ans)
# Original solution
# Acceptance of input
import sys

file_input = sys.stdin

V, E = list(map(int, file_input.readline().split()))

max_d = 1001
adj = [[] for i in range(V)]

for line in file_input:
    s, t, d = list(map(int, line.split()))
    adj[s].append((t, d))

max_path = 15001
dp = [[max_path] * (1 << V) for i in range(V)]
dp[0][0] = 0

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return None
    
    for t, d in adj[v]:
        if b & (1 << t):
            continue
        mask = b | (1 << t)
        t_d = dp[v][b] + d
        if dp[t][mask] > t_d:
            dp[t][mask] = t_d
            tsp(t, mask)

# Output
tsp(0, 0)

ans = dp[0][-1]
if ans == max_path:
    print((-1))
else:
    print(ans)

# Optimized solution
import sys

file_input = sys.stdin

V, E = list(map(int, file_input.readline().split()))

no_route = 15001

# (v-1) th vertex is excluded
dp = [[no_route] * (V - 1) for i in range(1 << (V - 1))]

adj = [[] for i in range(V)]

for line in file_input:
    s, t, d = list(map(int, line.split()))
    if s == V - 1:
        # Record the distance from the (v-1) th vertex to the adjacent vertex
        dp[1 << t][t] = d
    else: 
        # Store distance from source, not target
        adj[t].append((s, d))

# DP
for b in range(1, 1 << (V - 1)):
    for i in range(V - 1):
        b_i = 1 << i
        if b & b_i:
            pre_bit = b ^ b_i
            dp_pre = dp[pre_bit]
            for s, d in adj[i]:
                pre_rec = dp_pre[s]
                if pre_rec != no_route:
                    dp[b][i] = min(dp[b][i], pre_rec + d)

ans = no_route

# A state where all vertices other than (v-1) have been visited.
dp_comp = dp[(1 << (V - 1)) - 1]

for s, d in adj[V - 1]:
    comp_rec = dp_comp[s]
    if comp_rec != no_route:
        ans = min(ans, comp_rec + d)

if ans == no_route:
    print((-1))
else:
    print(ans)
# Original solution
def solve():
    from heapq import heappop, heappush
    V, E = list(map(int, input().split()))
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = list(map(int, input().split()))
        edges[s].append((t, d))

    result = float("inf")
    for i in range(V):
        q = [(0, i, {i})]
        while q:
            cost, v, visited = heappop(q)
            if len(visited) < V:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        heappush(q, (cost+d_cost, dest, visited | {dest}))
            elif len(visited) == V:
                for dest, d_cost in edges[v]:
                    if dest == i:
                        heappush(q, (cost+d_cost, i, visited | {-1}))
            else:
                if result > cost:
                    result = cost
                break

    print((result if result < float("inf") else -1))


if __name__ == "__main__":
    solve()

# Optimized solution
def solve():
    V, E = list(map(int, input().split()))
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = list(map(int, input().split()))
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 80
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print((result if result < float("inf") else -1))


if __name__ == "__main__":
    solve()
# Original solution
def solve():
    V, E = list(map(int, input().split()))
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = list(map(int, input().split()))
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 80
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print((result if result < float("inf") else -1))


if __name__ == "__main__":
    solve()

# Optimized solution
def solve():
    V, E = list(map(int, input().split()))
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = list(map(int, input().split()))
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 70
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print((result if result < float("inf") else -1))


if __name__ == "__main__":
    solve()
# Original solution
V, E = list(map(int, input().split()))
g = [[] for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    g[s].append((t, d))
INF = 10**9
dp = [[-1]*V for i in range(2**V)]
tmp = {}
def dfs(state, v, s):
    if dp[state][v] != -1:
        return dp[state][v]
    if state == 2**V-1:
        for t, d in g[v]:
            if t==s:
                dp[state][v] = d
                return d
        return INF
    res = INF
    idx = -1
    for t, d in g[v]:
        if state & (1 << t):
            continue
        r = dfs(state | (1 << t), t, s) + d
        if r < res:
            idx = t
        res = min(res, r)

    tmp[state, v] = (idx, res)

    return res
def solve(v):
    global dp
    dp = [[-1]*V for i in range(2**V)]
    return dfs(1<<v, v, v)
res = min(solve(v) for v in range(V))
print(res if res<INF else -1)

# Optimized solution
V, E = list(map(int, input().split()))
g = [[] for i in range(V)]
cost = {}
for i in range(E):
    s, t, d = list(map(int, input().split()))
    g[s].append((t, d))
    cost[s,t] = d
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = [[-1]*V for i in range(2**V)]
def dfs(state, v, s):
    if dp[state][v] != -1:
        return dp[state][v]
    if state == ALL:
        res = get((v, s), INF)
        dp[state][v] = res
        return res
    res = INF
    for t, d in g[v]:
        if not state & (1 << t):
            res = min(res, dfs(state | (1 << t), t, s) + d)
    dp[state][v] = res
    return res
def solve(v):
    global dp
    dp = [[-1]*V for i in range(2**V)]
    return dfs(1<<v, v, v)
res = min(solve(v) for v in range(V))
print(res if res<INF else -1)
# Original solution
import sys
readline = sys.stdin.readline
V, E = list(map(int, readline().split()))
g = [[] for i in range(V)]
cost = {}
to = [0]*V
for i in range(E):
    s, t, d = list(map(int, readline().split()))
    g[s].append((t, d))
    cost[s,t] = d
    to[s] |= 1 << t
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = {}
start = -1
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        res = get((v, start), INF)
        dp[key] = res
        return res
    if state & to[v] != to[v]:
        res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t)))
    else:
        res = INF
    dp[key] = res
    return res
def solve(v):
    global dp, start
    dp = {}
    start = v
    return dfs(1<<v, v)
res = min(solve(v) for v in range(V))
print(res if res<INF else -1)

# Optimized solution
import sys
readline = sys.stdin.readline
V, E = list(map(int, readline().split()))
g = [[] for i in range(V)]
cost = {}
to = [0]*V
for i in range(E):
    s, t, d = list(map(int, readline().split()))
    g[s].append((t, d))
    cost[s,t] = d
    to[s] |= 1 << t
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = {}
start = 0
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        dp[key] = res = get((v, start), INF)
        return res
    dp[key] = res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t))) if state & to[v] != to[v] else INF
    return res
res = dfs(1, 0)
print(res if res<INF else -1)
# Original solution
def dfs(g, last, vs, first):
    if vs:return min(g[last][v] + dfs(g, v, vs - {v}, first) for v in vs)
    else:return g[last][first]

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

v, e = list(map(int, readline().split()))
g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = list(map(int, readline().split()))
    g[s][t] = d

cost = []
vs = set(range(v))

first = 0
for second in range(1, v):
    if isinf(g[first][second]):continue
    cost.append(g[first][second] + dfs(g, second, vs - {first,second}, first))
        
ans = min(cost) if cost else -1
print((-1 if isinf(ans) else ans))

# Optimized solution
from sys import stdin
from math import isinf

readline = stdin.readline


min_cost = float('inf')


def main():
    v, e = list(map(int, readline().split()))
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = list(map(int, readline().split()))
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print((-1 if isinf(min_cost) else min_cost))


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost < cost:
        return
    if vs:
        for v in vs:
            if isinf(g[last][v]):
                continue
            dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:
        min_cost = cost + g[last][0]

main()
# Original solution
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

from collections import deque

def main():
    v, e = list(map(int, readline().split()))
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = list(map(int, readline().split()))
        g[s][t] = d
    min_cost = float('inf')

    que = deque([(0, 0, set(range(1, v)))])
    while que:
        cost, last, vs = que.pop()
        if min_cost <= cost:continue
        if vs:que.extend((cost + g[last][v], v, vs - {v}) for v in vs)
        elif min_cost > cost + g[last][0]:min_cost = cost + g[last][0]

    print((-1 if isinf(min_cost) else min_cost))

main()

# Optimized solution
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

min_cost = float('inf')

def main():
    v, e = list(map(int, readline().split()))
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = list(map(int, readline().split()))
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print((-1 if isinf(min_cost) else min_cost))


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost <= cost:return
    if vs:
        for v in vs:dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:min_cost = cost + g[last][0]

main()
# Original solution
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

min_cost = float('inf')

def main():
    v, e = list(map(int, readline().split()))
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = list(map(int, readline().split()))
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print((-1 if isinf(min_cost) else min_cost))


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost <= cost:return
    if vs:
        for v in vs:dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:min_cost = cost + g[last][0]

main()

# Optimized solution
# http://www.geocities.jp/m_hiroi/light/pyalgo65.html

def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def tsp(p, v):
    if (1 << point_size) - 1 == v:
        return distance_table[p][0]
    else:
        return min(distance_table[p][x] + tsp(x, v | (1 << x)) for x in range(point_size) if not (v & (1 << x)))

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

point_size, e = list(map(int, readline().split()))
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
for _ in range(e):
    s, t, d = list(map(int, readline().split()))
    distance_table[s][t] = d
ans = tsp(0,1)
print((-1 if isinf(ans) else ans))
# Original solution
v,e=list(map(int,input().split()))
dis=[[float("inf")]*v for _ in range(v)]
for i in range(e):
    s,t,d=list(map(int,input().split()))
    dis[s][t]=d
dp=[[float('inf')]*(v) for _ in range(1<<v)]
dp[1][0]=0
for i in range(1<<v):
    for j in range(v):
        if dp[i][j]==float('inf'):continue
        for k in range(v):
            if (i>>k)%2==1:continue
            nexti=i|1<<k
            nextdis=dp[i][j]+dis[j][k]
            dp[nexti][k]=min(dp[nexti][k],nextdis)
ans=float('inf')
for i in range(v):
    if dp[(1<<v)-1][i]==float('inf'):continue
    ans=min(ans,dp[(1<<v)-1][i]+dis[i][0])
if ans==float('inf'):
    print((-1))
else:
    print(ans)

# Optimized solution
v,e=list(map(int,input().split()))
dist=[[float("inf")]*v for _ in range(v)]
for i in range(e):
    s,t,d=list(map(int,input().split()))
    dist[s][t]=d

dp=[[float('inf')]*(v) for _ in range(1<<v)]
dp[1][0]=0
for i in range(1<<v):
    for j in range(v):
        if dp[i][j]==float('inf'):continue
        for k in range(v):
            if not (i>>k)&1:
                nexti=i|1<<k
                nextdist=dp[i][j]+dist[j][k]
                dp[nexti][k]=min(dp[nexti][k],nextdist)

ans=float('inf')
for i in range(v):
    if dp[(1<<v)-1][i]==float('inf'):continue
    ans=min(ans,dp[(1<<v)-1][i]+dist[i][0])
if ans==float('inf'):
    print((-1))
else:
    print(ans)
# Original solution
from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def calc_grandy(e):
  g = {}
  rev_g = defaultdict(set)
  rev_g[0] = set(range(1, N+1))
  for i in sorted(list(e.keys()), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      rev_g[m].add(i)
      rev_g[0].remove(i)
  return defaultdict(int, ((k,sum([pow(B, x, M) for x in v])%M) for k, v in list(rev_g.items())))

def get_edge():
  M = int(eval(input()))
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  grandy = list(map(calc_grandy, edge))
  ret = 0
  for gx, x in list(grandy[0].items()):
    for gy, y in list(grandy[1].items()):
      gz = gx^gy
      z = grandy[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(eval(input()))
edge = [get_edge() for i in range(3)]

print((solve(N, edge)))

# Optimized solution
from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(list(e.keys()), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def get_edge():
  M = int(eval(input()))
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, x in list(sum_g[0].items()):
    for gy, y in list(sum_g[1].items()):
      gz = gx^gy
      z = sum_g[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(eval(input()))
edge = [get_edge() for i in range(3)]

print((solve(N, edge)))
# Original solution
from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(list(e.keys()), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def get_edge():
  M = int(eval(input()))
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, x in list(sum_g[0].items()):
    for gy, y in list(sum_g[1].items()):
      gz = gx^gy
      z = sum_g[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(eval(input()))
edge = [get_edge() for i in range(3)]

print((solve(N, edge)))

# Optimized solution
from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(list(e.keys()), reverse=True):
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def read_edge():
  M = int(eval(input()))
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in list(sum_g[0].items()):
    for gy, sy in list(sum_g[1].items()):
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz)%M
  return ret

N = int(eval(input()))
edge = [read_edge() for i in range(3)]

print((solve(N, edge)))