Harryxun/stf_run huggingface dataset:
score_max, total = list(map(int, input().split()))
total //= 100
per_score_num = []
bonus = []
for i in range(score_max):
    inp = list(map(int, input().split()))
    per_score_num.append(inp[0])
    bonus.append(int(inp[1] / 100))
    

require = 0
min_cnt = np.inf


for bits in range(1 << score_max):
    solve_cnt = 0
    score = 0
    for i in range(score_max):
        if (1<<i)&bits:
            score += per_score_num[i] * (i+1)
            score += bonus[i]
            solve_cnt += per_score_num[i]
    if total > score:
        for j in range(score_max-1, -1, -1):
            if not (1<<j) & bits:
                require = math.ceil((total - score) // (j+1))
                if require < per_score_num[j]:
                    solve_cnt += require
                else:
                    solve_cnt = np.inf
                break
    min_cnt = min(min_cnt, solve_cnt)
print(min_cnt)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


d, g = LI()
g //= 100
p, c = list(zip(*LIR(d)))
c = [c[i] // 100 for i in range(d)]



ans = INF
for i in range(2 ** d):
    cnt = 0
    score = 0
    for j in range(d):
        if 1 << j & i:
            cnt += p[j]
            score += (j + 1) * p[j]
            score += c[j]


    max_score = -INF
    for k in range(d):
        if not (1 << k) & i:
            max_score = max(max_score, k + 1)
    if score < g:
        remain_num = (g - score) // max_score + bool((g - score) % max_score)
        if remain_num >= p[max_score - 1]:
            continue
        cnt += remain_num
    ans = min(ans, cnt)


print(ans)
a, b, h = map(int, input().split())
print((a+b)*h/2)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print((a+b)*h//2)
n = input()
chars = "Xabcdefghijklmnopqrstuvwxyz"
n_rem = n
ans = ""
 
while True:
  x = n_rem % 26
  if x == 0:
      x = 26
  ans += chars[x]
  n_rem -= x
  if n_rem == 0:
    break
  n_rem //= 26
print(ans[::-1])

### FIXED CODE ###

n = int(input())
chars = "Xabcdefghijklmnopqrstuvwxyz"
n_rem = n
ans = ""
 
while True:
  x = n_rem % 26
  if x == 0:
      x = 26
  ans += chars[x]
  n_rem -= x
  if n_rem == 0:
    break
  n_rem //= 26
  
print(ans[::-1])
n = int(input())
li1 = list(map(int, input().split()))

li2 = []
for i in range(1, len(li1)):
    li2.append(li1[i-1] - li1[i])
    
print(li2)

cnt1 = 0
cnt2 = 0
li3 = []
li4 = []

for i in li2:
    cnt2 += 1
    if i < 0:
        li3.append(cnt1)
        li4.append(cnt2)
        cnt1 = 0
    else:
        cnt1 += 1
    if cnt2 == len(li2):
        li3.append(cnt1)
        li4.append(cnt2)

print(max(li3))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n = int(input())
li1 = list(map(int, input().split()))

li2 = []
for i in range(1, len(li1)):
    li2.append(li1[i-1] - li1[i])
    
cnt1 = 0
cnt2 = 0
li3 = []

for i in li2:
    cnt2 += 1
    if i < 0:
        li3.append(cnt1)
        cnt1 = 0
    else:
        cnt1 += 1

li3.append(cnt1)

print(max(li3))
temparr = input()
temparr = temparr.split()
n = int(temparr[0])
k = int(temparr[1])
temparr = input()
import math
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(int(i))
arr = sorted(arr)
#print(arr)

left = 0 
right = arr[-1] + 1
ans = arr[-1]
while left <= right:
    mid = (left + right) // 2 
    count = 0 
    for i in arr :
        if i <= mid:
            continue 
        else:
            count += math.ceil(i / mid) - 1 
    if count <= k :
        right = mid - 1 
        if mid < ans:
            ans = mid 
    else:
        left = mid + 1 
print(ans)







### FIXED CODE ###

temparr = input()
temparr = temparr.split()
n = int(temparr[0])
k = int(temparr[1])
temparr = input()
import math
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(int(i))
arr = sorted(arr)
#print(arr)

left = 1
right = arr[-1] + 1
ans = arr[-1]
while left <= right:
    mid = (left + right) // 2 
    count = 0 
    for i in arr :
        if i <= mid:
            continue 
        else:
            count += math.ceil(i / mid) - 1 
    if count <= k :
        right = mid - 1 
        if mid < ans:
            ans = mid 
    else:
        left = mid + 1 
print(ans)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from numpy.fft import fft, ifft
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

S = np.array(S)

L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]


for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			L[i][j] = 0
		elif j == 0:
			L[i][j] = 1
		else:
			L[i][j] = L[i][j-1] + 1

for i in range(H):
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			R[i][j] = 0
		elif j == W-1:
			R[i][j] = 1
		else:
			R[i][j] = R[i][j+1] + 1

for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			U[i][j] = 0
		elif i == 0:
			U[i][j] = 1
		else:
			U[i][j] = U[i-1][j] + 1

for i in range(H-1, -1, -1):
	for j in range(W):
		if S[i][j] == '#':
			D[i][j] = 0
		elif i == H-1:
			D[i][j] = 1
		else:
			D[i][j] = D[i+1][j] + 1

L = np.array(L)
R = np.array(R)
U = np.array(U)
D = np.array(D)

print((L+R+U+D).max()-3)


### FIXED CODE ###

import sys
# from collections import deque, defaultdict, Counter
# from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
# from itertools import permutations, combinations, product
# from operator import itemgetter, mul
# from copy import deepcopy
# from string import ascii_lowercase, ascii_uppercase, digits
# from numpy.fft import fft, ifft
# from fractions import gcd
# import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			L[i][j] = 0
		elif j == 0:
			L[i][j] = 1
		else:
			L[i][j] = L[i][j-1] + 1

for i in range(H):
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			R[i][j] = 0
		elif j == W-1:
			R[i][j] = 1
		else:
			R[i][j] = R[i][j+1] + 1

for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			U[i][j] = 0
		elif i == 0:
			U[i][j] = 1
		else:
			U[i][j] = U[i-1][j] + 1

for i in range(H-1, -1, -1):
	for j in range(W):
		if S[i][j] == '#':
			D[i][j] = 0
		elif i == H-1:
			D[i][j] = 1
		else:
			D[i][j] = D[i+1][j] + 1

# L = np.array(L)
# R = np.array(R)
# U = np.array(U)
# D = np.array(D)

ans = 0
for i in range(H):
	for j in range(W):
		ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)
# print((L+R+U+D).max()-3)
S = input()
mod = 10 ** 9 + 7
def DP(i, j, S, mod):
    if i == len(S) and j == 3:
        return 1
    elif i == len(S) and j < 3:
        return 0
    elif i < len(S) and j == 3:
        if S[i] == "?":
            return 3 * DP(i+1, 3, S, mod) % mod
        else:
            return DP(i+1, 3, S, mod) % mod
    elif i < len(S) and j < 3:
        ABC = "ABC"
        if S[i] == "?":
            return (3 * DP(i+1, j, S, mod) + DP(i+1, j+1, S, mod)) % mod
        elif S[i] == ABC[j]:
            return (DP(i+1, j, S, mod) + DP(i+1, j+1, S, mod)) % mod
        else:
            return DP(i+1, j, S, mod) % mod

print(DP(0, 0, S, mod))

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)
#d  tree
n,k =  [int(i) for i in input().split()]
a   =  [int(i)-1 for i in input().split()]

#this is directed tree so every node is not reached yet
def dfs(u, d):
    change = 0
    if d>k:
        d = 1
        change += 1
    for v in edges[u]:
        change += dfs(v, d+1)
    return change


cnt = 0
if a[0]!=0:
    cnt += 1

edges = [[] for _ in range(n)]
for i in range(1,n):
    pa = a[i]
    edges[a[i]].append(i)   

cnt += dfs(0,0)    
print(cnt)

### FIXED CODE ###

#d  tree
#code自体はあっている。ただ、そもそもアルゴリズムが違う。
#下から調べていかないと最適でない。
#Right Answer. 
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

n,k =  [int(i) for i in input().split()]
a   =  [int(i)-1 for i in input().split()]

#this is directed tree so every node is not reached yet
#return the depth from its lowest bottom
def dfs(u):
    global cnt
    depth = 0 #default, this value is used when bottom
    
    for v in edges[u]:
        depth = max(depth, (dfs(v)+1)%k) #apply the maximum depth
        #because the edge was alerady cut, by the following procedure
    
    if depth==k-1 and u!=0 and a[u] != 0:
        cnt += 1
        
    return depth


cnt = 0
if a[0]!=0:
    cnt += 1

edges = [[] for _ in range(n)]
for i in range(1,n):
    pa = a[i]
    edges[a[i]].append(i)   

dfs(0)    
print(cnt)
S = [-1]*(101010)
def opt_S(h,n):
    if(n == 0):return 0
    elif(n == 1):return abs(h[1]-h[0])
    else :
        if(S[n] != -1):return S[n]
        s1 = opt_S(h,n-1) + abs(h[n-1]-h[n])
        s2 = opt_S(h,n-2) + abs(h[n-2]-h[n])
        S[n] = min(s1,s2)
        return S[n]



N = int(input())
h = list(map(int,input().split()))
print(opt_S(h,N-1))



### FIXED CODE ###

import sys
sys.setrecursionlimit(200000) #追加
S = [-1]*(101010)
def opt_S(h,n):
    if(n == 0):return 0
    elif(n == 1):return abs(h[1]-h[0])
    else :
        if(S[n] != -1):return S[n]
        s1 = opt_S(h,n-1) + abs(h[n-1]-h[n])
        s2 = opt_S(h,n-2) + abs(h[n-2]-h[n])
        S[n] = min(s1,s2)
        return S[n]



N = int(input())
h = list(map(int,input().split()))
print(opt_S(h,N-1))
class UnionFind():
    def __init__(self, n):
        self.p = list(range(n))
    
    def find(self, x):
        if self.p[x] == x:  return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:  self.p[x] = y

N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(1, N):
    if uf.find(0) != uf.find(i):
        uf.unite(0, i)
        ans += 1

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e9))

class UnionFind():
    def __init__(self, n):
        self.p = list(range(n))
    
    def find(self, x):
        if self.p[x] == x:  return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:  self.p[x] = y

N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(1, N):
    if uf.find(0) != uf.find(i):
        uf.unite(0, i)
        ans += 1

print(ans)
input!!!!
good!

### FIXED CODE ###

h,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(10)]
li = [list(map(int,input().split())) for i in range(h)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            if lis[i][j] > lis[i][k] + lis[k][j]:
                lis[i][j] = lis[i][k] + lis[k][j]
ans = 0
for i in range(h):
    for num in li[i]:
        if num >= 0:
            ans += lis[num][1]
print(ans)
N,R = input().split()
if N > 10:
  print(R)
else:
  print(R + (100 * (10 - N)))

### FIXED CODE ###

N,R = map(int, input().split())
if N > 10:
  print(R)
else:
  print(R + (100 * (10 - N)))
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l,L=[],[]
  for x in h:
   l=[x]+l
   if x in d[v]:break
  while v!=x:
   for y in l:
    if v in d[y]:
     L,v=[v]+L,y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L));sys.exit()
 for u in d[v]:f(u,[u]+h,q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

### FIXED CODE ###


N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v, l):
    for u in d[v]:
        if u in pvs:
            return l + [u]
        if u in vs:
            continue
        pvs.add(u)
        vs.add(u)
        ll = dfs(u, l + [u])
        pvs.remove(u)
        if ll:
            return ll
    return False

d = [set() for _ in range(N)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a-1].add(b-1)

vs = set()
for i in range(N):
    if i in vs:
        continue
    vs.add(i)
    pvs = set([i])
    loop = dfs(i, [i])
#    print(i, loop, vs)
    if loop:
        break

import sys
#print(loop)
if not loop:
    print("-1")
    sys.exit()
else:
    ll = []
    lx = loop[-1]
    f = False
    for x in loop:
        if lx == x and not f:
            f = True
            continue
        if not f:
            continue
        ll.append(x)
    loop = ll

v2i = [-1 for _ in range(N)]
for i, v in enumerate(loop):
    v2i[v] = i

i = 0
vs = set()
ss = set()
lnum = len(loop)
ll = []
while True:
    v = loop[i]
    if i in vs:
        f = False
        loop = []
        for x in ll:
            if v == x:
                f = True
            if f:
                loop.append(x)
        break

    m = 0
#    print(v, d[v], v2i, ss, vs)
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[u] in ss:
            continue
        if v2i[v] > v2i[u]:
            m = max(lnum - v2i[v] + v2i[u], m)
        else:
            m = max(v2i[u] - v2i[v], m)
#        print(u, m, v2i[u])
    for j in range(m-1):
        ss.add((i + j + 1) % lnum)
    vs.add(i)
    ll.append(v)
#    print(i, m, loop)
    i = (i + m) % lnum
#    print(i)

print(len(loop))
for i in loop:
    print(i+1)
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<n or j<n:
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

### FIXED CODE ###

p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) and j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")
A,B,K = map(int,input().split())
li = list(range(A,B+1))

from_A = li[0:K]
to_B = li[-K::]

sum_li  = list(set(from_A + to_B))

for i in sum_li:
    print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())

if (b-a+1) > 2*k:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)
from math import gcd

N = int(input())
A = list(map(int, input().split()))
d = gcd(A[0], A[1])
for i in range(2, N):
    d = gcd(d, A[i])
print(d)

### FIXED CODE ###

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

N = int(input())
A = list(map(int, input().split()))
d = gcd(A[0], A[1])
for i in range(2, N):
    d = gcd(d, A[i])
print(d)
import sys


def CheckRangeInt(input_str,_min,_max):

    if input_str.isdecimal()==0 or int(input_str)<_min or int(input_str)>_max:
        print("error")
        sys.exit()

    return int(input_str)


def CheckRangeList(input_list,_min,_max):
    for i in range(len(input_list)) :
        if H[i]<_min or H[i]>_max :
            print("error")
            sys.exit()
    return input_list

N=input()
N=CheckRangeInt(N,1,20)


H=list(map(int,input().strip().split()))
if len(H)!=N :
    print("error")
    sys.exit()
H=CheckRangeList(H,1,100)

highest=0
can_see=0

for i in range(N):
    if H[i]>=highest :
	can_see=can_see+1
        highest=H[i]

print(can_see)


### FIXED CODE ###

import sys


def CheckRangeInt(input_str,_min,_max):

    if input_str.isdecimal()==0 or int(input_str)<_min or int(input_str)>_max:
        print("error")
        sys.exit()

    return int(input_str)


def CheckRangeList(input_list,_min,_max):
    for i in range(len(input_list)) :
        if H[i]<_min or H[i]>_max :
            print("error")
            sys.exit()
    return input_list

N=input()

# if N.isdecimal()==0 or int(N)<1 or int(N)>20:                                                                                                                                                             
#     print("error")                                                                                                                                                                                        
#     sys.exit()                                                                                                                                                                                            

# N=int(N)                                                                                                                                                                                                  
N=CheckRangeInt(N,1,20)


H=list(map(int,input().strip().split()))

if len(H)!=N :
    print("error")
    sys.exit()

# for i in range(N) :                                                                                                                                                                                       
#     if H[i]<1 or H[i]>100 :                                                                                                                                                                               
#         print("error")                                                                                                                                                                                    
#         sys.exit()                                                                                                                                                                                        

H=CheckRangeList(H,1,100)

highest=0
can_see=0

for i in range(N):
    if H[i]>=highest :
        can_see=can_see+1
        highest=H[i]

print(can_see)
from itertools import groupby

N = int(input())
S = input()

print(len(groupby(S)))

### FIXED CODE ###

from itertools import groupby

N = int(input())
S = input()

print(sum(1 for k, _ in groupby(S)))
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
 
@lru_cache(maxsize = None)

N = int(input())
hlist = list(map(int, input().split()))
 
#再帰
"""
def function(n)
if 終了条件 return 初項
return function(n-1)を処理したもの
"""
def dp(n):
  if n==0: return 0
  if n==1: return abs(hlist[1] - hlist[0])
  else: return min(dp(n-1)+abs(hlist[n]-hlist[n-1]), dp(n-2)+abs(hlist[n]-hlist[n-2]))
 
print(dp(N-1))

### FIXED CODE ###

N = int(input())
hlist = list(map(int, input().split()))
cost = [-1 for _ in range(N)]

def dp(n):
  if n==0: return 0
  if n==1: return abs(hlist[1] - hlist[0])
  else: return min(cost[n-1]+abs(hlist[n]-hlist[n-1]), cost[n-2]+abs(hlist[n]-hlist[n-2]))

for i in range(N):
  cost[i]=dp(i)
print(cost[-1])
n,m=map(int,input().split())

ab = [map(int, input().split()) for _ in range(m)]
a,b = [list(i) for i in zip(*ab)]

indexlist=[-1]*n

def findroot(x):
    while 1:
        if indexlist[x-1] < 0:
            return x
        else:
            x=indexlist[x-1]
            


def merge(a,b):
    art=findroot(a)
    brt=findroot(b)
    art_ix=indexlist[art-1]
    brt_ix=indexlist[brt-1]
    if not art_ix<0 == brt_ix<0:
        indexlist[art-1]+=brt_ix
        indexlist[brt-1]=a
        return
    else:
        return
        

for j in range(m):
    a1=a[j]
    b1=b[j]
    merge(a1,b1)

ans=min(indexlist)*(-1)
print(ans)

### FIXED CODE ###

import sys

#UnionFindTreeクラスの定義
class UnionFind():
    #クラスコンストラクタ
    #selfはインスタンス自身
    def __init__(self, n):
        #親ノードを-1に初期化する
        self.parents = [-1] * n

    #根を探す（再帰関数）
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #xとyの木を併合する
    def union(self, x, y):
        #x,yの根をX,Yとする
        X = self.find(x)
        Y = self.find(y)

        #根が同じなら結合済み
        if X == Y:
            return

        #ノード数が多い方をXとする
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        #XにYのノード数を足す
        self.parents[X] += self.parents[Y]
        #Yの根をXとする
        self.parents[Y] = X


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#UnionFindインスタンスの生成
uf = UnionFind(N)
for a, b in info:
    #インデックスを調整し、a,bの木を結合
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)
n=int(input())
alist = [int(i) for i in input().split()]
ans=0

for i in range(n):
	if alist[i]==i+1:
		temp=alist[i+1]
		alist[i+1]=alist[i]
		alist[i]=temp
		ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
alist = [int(i) for i in input().split()]
ans=0
 
for i in range(n-1):
	if alist[i]==i+1:
		temp=alist[i+1]
		alist[i+1]=alist[i]
		alist[i]=temp
		ans+=1
if alist[n-1]==n:
	ans+=1
print(ans)