Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = (dp[i-1][j-1] + si) if si==tj else (dp[i-1][j] if len(dp[i-1][j]) > len(dp[i][j-1]) else dp[i][j-1])
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

# @profile
def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  # dp = numpy.zeros((len(s)+1, len(t)+1))
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

  lcs = ''
  i, j = len(s), len(t)
  while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
      i -= 1
    elif dp[i][j] == dp[i][j-1]:
      j -= 1
    else:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np
n, k, q = map(int,input().split())
a=[int(input()) for i in range(q)]
a = np.asarray(a)
list = np.ones(n)*k
for i in range(q):
  list = list - 1
  list[a[i]-1] = list[a[i]-1] + 1
for i in range(n):
  if 0<list[i]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

import numpy as np
def main():
  n, k, q = map(int,input().split())
  a=[int(input()) for i in range(q)]
  a = np.asarray(a)
  list = np.ones(n)*k
  list = list - q
  for i in range(q):
    list[a[i]-1] = list[a[i]-1] + 1
  for i in range(n):
    if 0<list[i]:
      print('Yes')
    else:
      print('No')

if __name__ == '__main__':
  main()
### BUGGY CODE ###

h,w = map(int,input().split())
A = []
for _ in range(h):
    a = list(map(int,input().split()))
    A.append(a)
B = []
for _ in range(h):
    b = list(map(int,input().split()))
    B.append(b)
g = [[0]*(w+1) for _ in range(h+1)]
m = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        m = max(m,abs(A[i-1][j-1]-B[i-1][j-1]))
        g[i][j] = abs(A[i-1][j-1]-B[i-1][j-1])
m *= (h+w)//2
dp = [[[False for _ in range(m+1)] for _ in range(w+1)] for _ in range(h+1)]
dp[1][1][g[1][1]] = True

for i in range(1,h+1):
    for j in range(1,w+1):
        for k in range(m+1):
            if k + g[i][j]<m:
                dp[i][j][k] = dp[i][j][k] or dp[i-1][j][abs(k-g[i][j])] or dp[i-1][j][k+g[i][j]] or dp[i][j-1][abs(k-g[i][j])] or dp[i][j-1][k+g[i][j]]
            else:
                dp[i][j][k] = dp[i][j][k] or dp[i-1][j][abs(k-g[i][j])] or dp[i][j-1][abs(k-g[i][j])]
            

for k in range(m+1):
    if dp[-1][-1][k]:
        print(k);exit()



### FIXED CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)//2 + 1
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        break
### BUGGY CODE ###

n = int(input())
s = input()
min = 30000000
for i in range(1,n-1):
    be = s[:i]
    af = s[i+1:n]
    cont = 0
    for j in range(len(be)):
        if be[j] == 'W':
            cont += 1
    for k in range(len(af)):
        if af[k] == 'E':
            cont += 1
    if cont < min:
        min = cont

a = s[1:n]
cont = 0
for w1 in range(n-1):
    if a[w1] == 'E':
        cont += 1
if cont < min:
    min = cont

a = s[:n-1]
cont = 0
for w2 in range(n-1):
    if a[w2] == 'W':
        cont += 1
if cont < min:
    min = cont

print(min)

### FIXED CODE ###

n = int(input())
s = input()
min = 0
for i in range(1,n):
    if s[i] == 'E':
        min += 1
cont = min
for j in range(1,n):
    if s[j-1] == 'W':
        cont += 1
    if s[j] == 'E':
        cont -= 1
    if cont < min:
        min = cont
print(min)
### BUGGY CODE ###

# Author: cr4zjh0bp
# Created: Sat Mar 14 14:07:54 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N = ni()
m = 3500 // 4

def f():
    ans = []
    for h in range(3501):
        for n in range(3501):
            c = h * n * N
            d = 4 * h * n - N * n - N * h
            if d > 0 and c % d == 0:
                ans = [h, n, c // d]
                return ans

print(*f())

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Sat Mar 14 14:07:54 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N = ni()
m = 3500 // 4

def f():
    ans = []
    for h in range(3501):
        for n in range(3501):
            c = h * n * N
            d = 4 * h * n - N * n - N * h
            if d > 0 and c % d == 0:
                ans = [h, n, c // d]
                return ans

print(*f())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())

g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

def dfs(now, prev=-1):
    for next in g[now]:
        if next == prev:
            continue

        c[next] += c[now]
        dfs(next, now)

dfs(0)
print(*c)

### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())

g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

q = deque([0])
flag = [False] * n
while q:
    v = q.pop()
    flag[v] = True
    for e in g[v]:
        if flag[e]:
            continue
        c[e] += c[v]
        q.append(e)

print(*c)
### BUGGY CODE ###

import bisect

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans = 0

for i in a:
  indb = bisect.bisect_right(b,i)
  for j in range(indb,len(b)):
    indc = bisect.bisect_right(c,b[j])
    ans += n - indc
    
print(ans)

### FIXED CODE ###

import bisect
import itertools

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
bc = []
ans = 0
count = 0


for i in b:
  indc = bisect.bisect_right(c,i)
  bc.append((n - indc))
  count += 1

BC = [0] + list(itertools.accumulate(bc))

for i in a:
  indb = bisect.bisect_right(b,i)
  ans += BC[-1] - BC[indb]
   
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

# sum of deliciousness が border以上の組み合わせが K個以上あればTrue
def is_ok(a, b, c, X, Y, Z, K, border):
    cnt = 0
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                if a[i] + b[j] + c[k] < border:
                    break
                cnt += 1
                if cnt >= K:
                    return True
    return False

def main():
    x, y, z, K = map(int, sys.stdin.readline().split())
    abc = np.array(sys.stdin.read().split(), dtype=np.int64)
    a = abc[:x]
    b = abc[x:x + y]
    c = abc[x + y:x + y+ z]
    a = np.sort(a)[::-1]
    b = np.sort(b)[::-1]
    c = np.sort(c)[::-1]

    l, r = 3, 3 * 10 ** 10
    while l <= r:
        border = (l + r) // 2
        if is_ok(a, b, c, x, y, z, K, border):
            l = border + 1
        else:
            r = border - 1

    res = []
    cnt = 0
    for i in range(x):
        for j in range(y):
            for k in range(z):
                sum_deli = a[i] + b[j] + c[k]
                if sum_deli < r:
                    break
                res.append(sum_deli)
                cnt += 1
                if cnt >= K:
                    break
                

    res = sorted(res, reverse=True)[:K]
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import numpy as np
from heapq import heappush, heappop


def main():
    x, y, z, K = map(int, sys.stdin.readline().split())
    abc = np.array(sys.stdin.read().split(), dtype=np.int64)
    a = abc[:x]
    b = abc[x:x + y]
    c = abc[x + y:x + y+ z]
    a = np.sort(a)[::-1]
    b = np.sort(b)[::-1]
    c = np.sort(c)[::-1]

    hq = []
    heappush(hq, (-(a[0]+b[0]+c[0]), 0, 0, 0))
    res = []
    added_before = set()
    # setで確認をO(1)でする
    added_before.add((0, 0, 0))

    for _ in range(K):
        sum_deli, i, j, k = heappop(hq)
        res.append(-sum_deli)
        if i < x - 1 and not (i+1, j, k) in added_before:
            heappush(hq, (-(a[i+1]+b[j]+c[k]), i+1, j, k))
            added_before.add((i+1, j, k))
        if j < y - 1 and not (i, j+1, k) in added_before:
            heappush(hq, (-(a[i]+b[j+1]+c[k]), i, j+1, k))
            added_before.add((i, j+1, k))
        if k < z - 1 and not (i, j, k+1) in added_before:
            heappush(hq, (-(a[i]+b[j]+c[k+1]), i, j, k+1))
            added_before.add((i, j, k+1))

    for s_deli in res:
        print(s_deli)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

a, b, x = [int(_) for _ in input().split()]

count = 0

for n in range(a, b+1):
    if (n % x) == 0:
        count += 1

print(count)

### FIXED CODE ###

a, b, x = [int(_) for _ in input().split()]

count = b//x - a//x

if a%x == 0:
    count += 1

print(count)
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))[:n]

r=1

for i,j in enumerate(a[1:],1):
    # print('aaaaa')
    # print(i,j)
    is_b=False
    for y in a[:i]:
        if y < j:
            is_b=True
            break
    if not is_b:
        r+=1

print(r)


### FIXED CODE ###

n=int(input())

a = list(map(int,input().split()))[:n]

r=1
min=a[0]

for i in range(1,n):
    if a[i] > min:continue
    else:
        r+=1
        min=a[i] 
    

print(r)
### BUGGY CODE ###

x=int(input())
i=0
a=[]
while x>=i**2:
    i+=1
    a.append((i-1)**2)
    j=0
    while x>=i**j:
        j+=1
        a.append((i-1)**j)
print(max(a))

### FIXED CODE ###

x=int(input())
i,j=2,1
ans=[]
if x==1:
    print(1)
    quit()
while True:
    j+=1
    if i**j>x:
        i+=1
        j=2
        if i**j>x:
            break
    ans.append(i**j)
print(max(ans))
### BUGGY CODE ###

n = int(input())
s = input()

rcnt = s.count('R')
gcnt = s.count('G')
bcnt = s.count('B')

sub = 0
for i in range(n):
    for j in range(i+1, n):
        k = j + (j - i)
        if n <= k: break

        alp = set()
        alp.add(s[i])
        alp.add(s[j])
        alp.add(s[k])

        if len(alp) == 3: sub += 1

ans = rcnt * gcnt * bcnt - sub
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

rcnt = s.count('R')
gcnt = s.count('G')
bcnt = s.count('B')

sub = 0
for i in range(n):
    for j in range(i+1, n):
        k = j + (j - i)
        if n <= k: break

        alp = set()
        alp.add(s[i])
        alp.add(s[j])
        alp.add(s[k])

        if len(alp) == 3: sub += 1

ans = rcnt * gcnt * bcnt - sub
print(ans)
### BUGGY CODE ###

n = int(input())

factorial = 1
divisor = []
ans = 0

for i in range(1,n+1):
    factorial = factorial * i

for i in range(1,factorial+1):
    if factorial % i == 0:
        divisor.append(i)

# print(divisor)

ans = len(divisor) % (10 ** 9 + 7)

print(ans)

### FIXED CODE ###

import math
import collections

n = int(input())

factorial = 1
divisor = []
ans = 1


# 素数を求める関数
def get_prime(num):
    if num <= 1:
        return
    for i in range(2, num+1):
        while num % i == 0:
            divisor.append(i)
            num //= i


# 約数の数 = (素数xの個数+1)(素数yの個数+1)(素数zの個数+1)...
# 方針：入力値を素因数分解し、各素因数の個数を求める

# n-iの素因数を求める
for j in range(2, n+1):
    get_prime(j)

# print(divisor)

# 各素因数の組み合わせ数を求める
count = collections.Counter(divisor)

for k in count.most_common():
    temp = list(k)[1]
    ans = ans * (temp + 1)

ans = ans % (10 ** 9 + 7)

print(ans)
### BUGGY CODE ###

def f(a,p1,p2):
    if p1>p2:
        return 0
   
    return max(a[p1]+min(f(a,p1+2,p2),f(a,p1+1,p2-1))
                      ,a[p2]+min(f(a,p1+1,p2-1),f(a,p1,p2-2)))
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
first=f(a,0,n-1)
print(first-(s-first))
                             


### FIXED CODE ###

def f(a,i,j,dp):
    if dp[i][j]==-1:
        if i>j:
            return 0

        dp[i][j]=max(a[i]+min(f(a,i+2,j,dp),f(a,i+1,j-1,dp)),
                                a[j]+min(f(a,i+1,j-1,dp),f(a,i,j-2,dp)))
    return dp[i][j]
        
n=int(input())
dp=[[-1 for i in range(n)] for j in range(n)]
a=list(map(int,input().split()))
for i in range(n):
    dp[i][i]=a[i]

for i in range(n-1):
    dp[i][i+1]=max(a[i],a[i+1])

s1=f(a,0,n-1,dp)

print(s1-sum(a)+s1)
### BUGGY CODE ###

def main():
    
    N,W = map(int,input().split())
    array = []
    for i in range(N):
        wv = list(map(int,input().split()))
        array.append(wv)
    dp = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j-array[i][0] >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
            else:
                dp[i+1][j] = dp[i][j]

    print(dp[-1][-1])
main()

### FIXED CODE ###

N,W = map(int,input().split())
array = []
for i in range(N):
    wv = list(map(int,input().split()))
    array.append(wv)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-array[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
### BUGGY CODE ###

#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def union(x,y):
    x = find(x)
    y = find(y)
    parent[x] = y

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x]= find(parent[x])
        return parent[x]



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)

### FIXED CODE ###

N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)
### BUGGY CODE ###

s = input()
n = len(s)
dp = [[0] * 2019 for _ in range(n + 1)]

for i in range(1, n + 1):
    x = int(s[i-1])
    dp[i][x] = 1
    for j in range(2019):
        dp[i][(j*10+x)%2019] += dp[i-1][j]

ans = 0

for i in range(1, n+1):
    ans += dp[i][0]

print(ans)

### FIXED CODE ###

s = input()
n = len(s)

res = 0
cnt = [0] * 2019
for i in range(n):
    res = (res + int(s[n-1-i]) * pow(10, i, 2019)) % 2019
    cnt[res] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
ans += cnt[0]

print(ans)
### BUGGY CODE ###

from collections import defaultdict
N,M = list(map(int,input().split()))
price_howmany = defaultdict(int)
for _ in range(N):
    tmp = list(map(int,input().split()))
    price_howmany[tmp[0]] += tmp[1]

price_howmany = dict(price_howmany)

def solve():
    price = 0
    many = 0
    global M
    while M > 0:
        low_price = min(price_howmany.keys())
        many = min(M,price_howmany[low_price])
        price += many * low_price
        M -= many
        price_howmany.pop(low_price)
    print(price)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

# from collections import defaultdict
# N,M = list(map(int,input().split()))
# price_howmany = defaultdict(int)
import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()
price_howmany = {}
# price_list = []

price_set = set()
for _ in range(N):
    tmp = read_int()
    # if tmp[0] not in price_set:
        # price_list.append(tmp[0])
    price_set.add(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
# price_list.sort(reverse=True)
price_list = sorted(list(price_set))

# price_howmany = dict(price_howmany)

def solve():
    price = 0
    global M
    # while M > 0:
        # low_price = min(price_howmany.keys())
        # low_price = price_list.pop()
        # many = min(M,price_howmany.pop(low_price))
        # price += many * low_price
        # M -= many
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

D = [[-1] * N for _ in range(N)]
for i in range(N - 1):
  a, b = ab[i][0] - 1, ab[i][1] - 1
  a, b = min(a, b), max(a, b)
  D[a][b] = i

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  L = T.dfs(x, y, r)
  n = L[0]
  t = 0
  for j in range(1, len(L)):
    m = L[j]
    x, y = min(n, m), max(n, m)
    t = t | (1 << D[x][y])
    n = m
  NL[i] = t
  

ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  D = [[0] * N for _ in range(N)]
  f = 0
  k = 0
  for j in range(M):
    if t & 1:
      f += 1
      k = k | NL[j]
    t >>= 1
  cnt = bin(k).count("1")
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))
print(ans - c)

### FIXED CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

D = [[-1] * N for _ in range(N)]
for i in range(N - 1):
  a, b = ab[i][0] - 1, ab[i][1] - 1
  a, b = min(a, b), max(a, b)
  D[a][b] = i

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  L = T.dfs(x, y, r)
  n = L[0]
  t = 0
  for j in range(1, len(L)):
    m = L[j]
    x, y = min(n, m), max(n, m)
    t = t | (1 << D[x][y])
    n = m
  NL[i] = t
  

ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  f = 0
  k = 0
  for j in range(M):
    if t & 1:
      f += 1
      k = k | NL[j]
    t >>= 1
  cnt = bin(k).count("1")
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))
print(ans - c)