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

import numpy as np
mapping = {
    "R": (1, 0),
    "L": (-1, 0),
    "U": (0, 1),
    "D": (0, -1)
}

def f(x, vx, t):
    nx = x + vx * t
    return np.max(nx) - np.min(nx)

def solve(n, x, y, d):
    lb = 0
    ub = 10**10
    x = np.asarray(x, dtype=np.float)
    y = np.asarray(y, dtype=np.float)
    vx = np.zeros(n, dtype=np.float)
    vy = np.zeros(n, dtype=np.float)
    for i in range(n):
        vx[i], vy[i] = mapping[d[i]]
    h = lambda t: f(y, vy, t) * f(x, vx, t)
    while abs(ub-lb) > 1e-9:
        t1 = (2*lb + ub) / 3
        t2 = (lb + 2*ub) / 3
        if h(t1) < h(t2):
            ub = t2
        else:
            lb = t1
    return (h(t1) + h(t2)) / 2

n = int(input())
x, y, d = [-1]*n, [-1]*n, [-1]*n
for i in range(n):
    x[i], y[i], d[i] = input().split()
    x[i] = int(x[i])
    y[i] = int(y[i])
print(solve(n, x, y, d))

### FIXED CODE ###

import numpy as np
from scipy.optimize import fmin

INF = 10**18

mapping = {
    "R": (1, 0),
    "L": (-1, 0),
    "U": (0, 1),
    "D": (0, -1)
}

def f(x, vx, t):
    if t < 0:
        return INF
    nx = x + vx * t
    return nx.max() - nx.min()

def solve(n, x, y, d):
    x = np.asarray(x, dtype=np.float)
    y = np.asarray(y, dtype=np.float)
    vx = np.zeros(n, dtype=np.float)
    vy = np.zeros(n, dtype=np.float)
    for i in range(n):
        vx[i], vy[i] = mapping[d[i]]
    h = lambda t: f(y, vy, t) * f(x, vx, t)
    t = fmin(h, x0=10**8, ftol=1e-9, disp=False)[0]
    return h(t)

n = int(input())
x, y, d = [-1]*n, [-1]*n, [-1]*n
for i in range(n):
    x[i], y[i], d[i] = input().split()
    x[i] = int(x[i])
    y[i] = int(y[i])
print(solve(n, x, y, d))
### BUGGY CODE ###

n=int(input())
x=input()
cntm=0
cntp=0
fn=0
xi=[0]*n
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        fn+=1
for i in reversed(range(n)):
    if x[i]=="1":
        cntp+=pow(2,n-i-1,fn+1)
        cntp%=fn+1
        if fn>1:
            cntm+=pow(2,n-i-1,fn-1)
            cntm%=fn-1
for i in reversed(range(n)):
    if x[i]=="1":
        if fn>1:
            xi[i]=(cntm-pow(2,n-i-1,fn-1))%(fn-1)
            ans[i]+=1
    else:
        xi[i]=(cntp+pow(2,n-i-1,fn+1))%(fn+1)
        ans[i]+=1
#print(xi)
for i in range(n):
    num=xi[i]
    while num>0:
        cnt=0
        for j in range(31):
            if (num>>j)&1:
                cnt+=1
        num%=cnt
        ans[i]+=1
    print(ans[i])

### FIXED CODE ###

n=int(input())
x=input()
cntm=0
cntp=0
fn=0
xi=[0]*n
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        fn+=1
for i in reversed(range(n)):
    if x[i]=="1":
        cntp+=pow(2,n-i-1,fn+1)
        cntp%=fn+1
        if fn>1:
            cntm+=pow(2,n-i-1,fn-1)
            cntm%=fn-1
for i in reversed(range(n)):
    if x[i]=="1":
        if fn>1:
            xi[i]=(cntm-pow(2,n-i-1,fn-1))%(fn-1)
            ans[i]+=1
    else:
        xi[i]=(cntp+pow(2,n-i-1,fn+1))%(fn+1)
        ans[i]+=1
#print(xi)
for i in range(n):
    num=xi[i]
    while num>0:
        cnt=0
        for j in range(31):
            if (num>>j)&1:
                cnt+=1
        num%=cnt
        ans[i]+=1
    print(ans[i])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    print(len([j for j in A if j == i+1]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(key=int)
l=0
for i in range(N):
    c=0
    while l < len(A) and A[l] == i+1:
        l+=1
        c+=1
    print(c)
### BUGGY CODE ###

import sys
import math
import bisect

input = sys.stdin.readline
ceil = math.ceil
rbisect=bisect.bisect_right
def main():
    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = rbisect(keys[i:],x+2*d)-1 ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[i+idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
ceil = math.ceil

def main():
    def isok(z,val):##適宜変更
        return (z-val<=2*d)
    def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok ##一番右のTrueのindex  Trueの個数はok+1こ

    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys,x) ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

# from scipy.misc import comb
# from scipy.special import comb
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def banned(al):
    d = {}
    for a in al:
        if a in d.keys():
            d[a] += 1
        else:
            d[a] = 1
    # print(d)
    for k, v in d.items():
        if v > 1:
            d[k] = [v, comb(v, 2)]
        else:
            d[k] = [v, 0]
    for a in al:
        ans = 0
        for k, v in d.items():
            if k == a:
                if v[0] > 2:
                    ans += comb(v[0]-1, 2)
            else:
                ans += v[1]
        print(int(ans))

n = int(input())
al = [int(i) for i in input().split()]

banned(al)

### FIXED CODE ###

# from scipy.misc import comb
# from scipy.special import comb
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def banned(al):
    d = {}
    for a in al:
        if a in d.keys():
            d[a] += 1
        else:
            d[a] = 1
    # print(d)
    ans = 0
    for k, v in d.items():
        if v > 1:
            ans += comb(v, 2)
            # d[k] = [v, comb(v, 2)]
        # else:
            # d[k] = [v, 0]
    # print(ans)
    for a in al:
        # for k, v in d.items():
        #     if k == a:
        #         if v[0] > 2:
        #             ans += comb(v[0]-1, 2)
        #     else:
        #         ans += v[1]
        print(int(ans-(d[a]-1)))

n = int(input())
al = [int(i) for i in input().split()]

banned(al)
### BUGGY CODE ###

s = input()
n = len(s)
alist = [int(s[i:])%2019 for i in range(n)] + [0]
from collections import Counter
a_counter = Counter(alist)
a_counter = a_counter.most_common()
ans = 0

for i in range(len(a_counter)):
    if a_counter[i][1] >= 2:
        ans += a_counter[i][1]*(a_counter[i][1]-1)//2
print(ans)


### FIXED CODE ###

s = input()[::-1]
a = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
for c in s:
    a += int(c) * d
    a %= 2019
    d *= 10
    d %= 2019
    cnt[a] += 1

#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


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

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

N = int(input())
M=1
for i in range(1,N):
    for j in range(2,N):
        if i**j<= N:
            M = max(M,i**j)
        else:
            break
print(M)
            

### FIXED CODE ###

N = int(input())
M=1
for i in range(1,N):
        if i**2<= N:
            M = max(M,i**2)
        else:
            break
print(M)
### BUGGY CODE ###

A,B = map(int, input().split())
ans = int(0)
for i in range(A,B+1):
  ans = ans ^ i
print(ans)

### FIXED CODE ###

import math

A,B = map(int, input().split())
ans = int(0)
if B==0:
  ans = 0
else:
  N = math.floor(math.log2(B)+1)
  
  A_mod = A % 4
  B_mod = B % 4
  if A_mod < 2:
    if B_mod ==1 or B_mod == 2:
      ans += 1
  else:
    if B_mod ==3 or B_mod == 0:
      ans += 1

  for i in range(2,N+1):
    A_mod = A % (2**i)
    B_mod = B % (2**i)
    if A_mod < 2**(i-1):
      if B_mod >= 2**(i-1):
        ans += ((B_mod+1)%2)*(2**(i-1))
    else:
      if B_mod < 2**(i-1):
        ans += (A_mod%2)*(2**(i-1))
      else:
        ans += ((A_mod+B_mod+1)%2)*(2**(i-1))

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

N = int(input())
A = list(map(int, input().split()))

if N == 1:
  print(1)
  exit(0)
#
A.sort()
A.append(0) 

b = []
ans = 0
i = 0

if A[0] ==1:
  if A[1] == 1:
    print(0)
  else:
    print(1)
  exit(0)
#
while i < N:
  c = A[i]
  for j in b:
    if c % j == 0:
      break
  else:
    b.append(c)
    if c != A[i+1]:
      ans += 1
  while c == A[i+1]:
    i += 1
  i += 1
#          
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

cnt = [0] * 1000001

for i in A:
  if cnt[i] == 1:
    continue 
  if cnt[i] == 2:
    cnt[i] = 1
    continue
  cnt[i] = 2
  for j in range( (i+i),1000001,i):
    cnt[j] = 1
#
ans = 0
for i in range(1000001):
  if cnt[i] == 2:
    ans += 1
#
print(ans)
### BUGGY CODE ###

from math import floor, sqrt


def func(x):
    return floor((sqrt(1 + 8 * x) - 1) / 2)


N = int(input())
limit = floor(sqrt(N))

primes = [2]

count = 0
flag = True
p = 2
while 1:
    #print(p,N)
    isprime = True
    if N == 1:
        break
    if p > sqrt(N):
        count += 1
        break
    if p > 3:
        for i in primes:
            if i >= sqrt(p):
                break
            if p % i == 0:
                isprime = False
                break
        if not isprime:
            p += 2
            continue
        primes.append(p)
    a = 0
    while N % p == 0:
        #print("while",p, a)
        a += 1
        N = N // p
    count += func(a)
    if p == 2:
        p = 3
    else:
        p += 2
print(count)





### FIXED CODE ###

from math import floor, sqrt


def func(x):
    return floor((sqrt(1 + 8 * x) - 1) / 2)


N = int(input())
limit = floor(sqrt(N))

primes = [2]

count = 0
flag = True
p = 2
while 1:
    #print(p,N)
    isprime = True
    if N == 1:
        break
    if p > sqrt(N):
        count += 1
        break
    
    a = 0
    while N % p == 0:
        #print("while",p, a)
        a += 1
        N = N // p
    count += func(a)
    if p == 2:
        p = 3
    else:
        p += 2
print(count)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))

out=[]
i =0
while i < N:
    out.append(i)
    for j,a in enumerate(A):
        if i!=j and A[i]%a==0:
            out.pop()
            break
    i += 1
print(len(out))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))

dp = [0] * (10**6+1)

for a in A:
    dp[a] += 1

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))

C = 0
for i in set(A):
  n = A.count(i)
  C += n * (n - 1) //2
  
for a in A:
  n = A.count(a)
  print(C - (n - 1))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))

ls = [0] * (N + 1)
for a in A:
  ls[a] += 1

C = 0
for i in set(A):
  n = ls[i]
  C += n * (n - 1) //2
  
for a in A:
  n = ls[a]
  print(C - (n - 1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

H,W,D = map(int,input().split())
N = H*W

# 各数値の書かれている位置, 1-indexed
X = [0] * (N+1)
Y = [0] * (N+1)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

X = np.array(X,dtype=np.int64)
Y = np.array(Y,dtype=np.int64)

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


Q = int(input())
output = []
for _ in range(Q):
  l,r = map(int,input().split())
  output.append(MAGIC[r] - MAGIC[l])

print('\n'.join(map(str,output)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

H,W,D = map(int,input().split())
N = H*W
ND = N//D

# 各数値の書かれている位置, 1-indexed
X = np.zeros((D,ND+1),dtype=np.int64)
Y = np.zeros((D,ND+1),dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    n = int(n)
    q,r = n//D,n%D
    X[r,q] = x
    Y[r,q] = y

# 0D+d から nD+d への移動コスト
MAGIC = np.zeros_like(X)
MAGIC[:,1:] = (np.abs(np.diff(X,axis = 1)) + np.abs(np.diff(Y,axis = 1))).cumsum(axis = 1)

Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  d = l%D
  print(MAGIC[d,r//D] - MAGIC[d,l//D])
### BUGGY CODE ###

from collections import Counter

n, m = map(int, input().split())
l = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append(sum(l[:i+1])%m)

c = Counter(s)

"""
ans = 0
while s:
    cnt = s.count(s[0])
    s = s[cnt:]
    ans += cnt*(cnt-1)//2

print(ans)
"""

ans = 0
for x in c.values():
    ans += x*(x-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

n, m = map(int, input().split())
l = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append((s[-1]+l[i])%m)

c = Counter(s)

ans = 0
for x in c.values():
    ans += x*(x-1)//2

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

import numpy as np
n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(min(k,50)):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    imos = list(np.cumsum(imos))[:-1]
    if set(imos)=={n}:
        break
print(*imos)


### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    for k in range(1, len(imos)):
        imos[k] = imos[k]+imos[k-1]
    imos = imos[:-1]
    if set(imos)=={n}:
        break
print(*imos)
### BUGGY CODE ###

l = raw_input().split()
#l=input[0].split()

n = int(l[0])
a = [2147483647]*n
change = 1

for i in range(0,int(l[1])):
	l = raw_input().split()
#	l=input[i+1].split()
	if int(l[0])==0:
		a[int(l[1])]=int(l[2])
		change = 1
	elif change==l[1]+l[2]:
		print m
	else:
		change = l[1]+l[2]
		m = min(a[int(l[1]):int(l[2])+1])
		print m

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
 
def main(init=int(2**31-1), readline=stdin.readline):
    n, q = (int(s) for s in readline().split())
 
    a = [init] * n
    b = [init] * ((n // 100) + 1)
 
    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            bx = x - (x % 100) + 100
            by = y - (y % 100)
            if bx < by:
                m = min(min(a[x:bx]), min(b[bx//100:by//100]),
                        min(a[by:y+1]))
            else:
                m = min(a[x:y+1])
            print(m)
        else:
            a[x] = y
            bx = x - (x % 100)
            b[x//100] = min(a[bx:bx+100])
 
 
main()
### BUGGY CODE ###

N, Y = map(int,input().split())
for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if Y == 10000*i + 5000*j + 1000*k and N == i + j + k:
        print(i," ",j," ",k)
        break
    else:
      continue
    break
  else:
    continue
  break
else:
  print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int,input().split())
for i in range(N+1):
  for j in range(N+1):
    if Y == 10000*i + 5000*j + 1000*(N-i-j) and N-i-j >= 0:
      print(i," ",j," ",N-i-j)
      break
  else:
    continue
  break
else:
  print("-1 -1 -1")
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
put = []

for i in reversed(range(N)):
    if A[i]:
        put.append(i+1)
        # iを素因数分解して、約数に1をxorしていく
        tmp = 1
        n = i+1
        while tmp*tmp <= n:
            if n % tmp == 0:
                A[tmp-1] ^= 1
                if tmp != n//tmp:
                    A[n//tmp-1] ^= 1
            tmp += 1


if len(put) > 0:
    print(len(put))
    print(*put)
else:
    print(0)


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = [0]*N
put = []

for i in reversed(range(N)):
    if A[i] != B[i]:
        put.append(i+1)
        # iを素因数分解して、約数に1をxorしていく
        tmp = 1
        n = i+1
        while tmp*tmp <= n:
            if n % tmp == 0:
                B[tmp-1] ^= 1
                if tmp != n//tmp:
                    B[n//tmp-1] ^= 1
            tmp += 1


if len(put) > 0:
    print(len(put))
    print(*put)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
P = [int(i) for i in input().rstrip().split(' ')]
c = 0
for i,p in enumerate(P):
    for q in P[:i+1]:
        if p > q:
           break
    else:
        c += 1
print(c)

### FIXED CODE ###

N = int(input())
P = [int(i) for i in input().rstrip().split(' ')]
c = 0
m = 2*10**5
for i,p in enumerate(P):
    if m >= p:
        m = p
        c += 1
print(c)
### BUGGY CODE ###

def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=2):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        for i in range(min(n, m)):
            if M[i][i] == 0:
                for j in range(i+1, n):
                    if M[j][i] != 0:
                        for k in range(i, m):
                            M[i][k] ^= M[j][k]
                        break
                else:
                    for j in range(i+1, m):
                        if M[i][j] != 0:
                            for k in range(i, n):
                                M[k][i] ^= M[k][j]
                            break
                    else:
                        rank -= 1
            M2 = M[i]
            for j in range(i+1, n):
                M3 = M[j][i]
                M[j][i] = 0
                for k in range(i+1, m):
                    M[j][k] ^= M3*M2[k]
        return rank

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
                    m2 += [ai]
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()


### FIXED CODE ###

def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
anslst = []
for i in range(Q):
    l1, l2 = map(int,input().split())
    compStr = S[l1 - 1:l2]
    anslst.append(compStr.count('AC'))

for i in anslst:
    print(i)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
mLst = [0] * N
for i in range(N - 1):
    if S[i: i + 2] == 'AC':
        mLst[i + 1] = mLst[i] + 1
    else:
        mLst[i + 1] = mLst[i]

lLst = [list(map(int, input().split())) for i in range(Q)]

for i in range(Q):
    print(mLst[lLst[i][1] - 1] - mLst[lLst[i][0] - 1])
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
F = sorted(list(map(int, input().split())))


def binary_search(min_n, max_n):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def judge(tn):

    k = 0
    for i in range(N):
        if A[i] * F[i] > tn:
            k += A[i] - (tn // F[i])
        if k > K:
            return False

    return True


def solve():

    ans = binary_search(-1, 10**12)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys

input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
F = sorted(list(map(int, input().split())))


def binary_search(min_n, max_n):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def judge(tn):

    k = 0
    for i in range(N):
        if A[i] * F[i] > tn:
            k += A[i] - (tn // F[i])
        if k > K:
            return False

    return True


def solve():

    ans = binary_search(-1, 10**12)
    print(ans)


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

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

A = []
B = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()

import math

Z = N * (N - 1) // 2

L = []
ans = []
for i in range(M):
    a, b = A[i], B[i]
    ia, ib = -1, -1
    for j in range(len(L)):
        if a in L[j]:
            ia = j
        if b in L[j]:
            ib = j
    if ia == -1 and ib == -1:
        L.append({a, b})
    elif ib != -1 and ia != -1 and ia != ib:
        L[ia] = L[ia].union(L[ib])
        del L[ib]
    elif ib != -1:
        L[ib].add(a)
    elif ia != -1:
        L[ia].add(b)
    else:
        print("Error?")

    # print(L)

    ans.append(Z - sum([(len(x) * (len(x) - 1)) // 2 for x in L]))

ans.reverse()
del ans[0]
ans.append(Z)

for a in ans:
    print(a)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = [int(x) for x in input().split()]
g = 0

A = []
B = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()


# ----- Union Find -----------
PARENT = list(range( N + 1 ))
SIZE = [1] * (N + 1 )

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2
    global g
    g = g + SIZE[n2] * SIZE[n1]
    SIZE[n2] += SIZE[n1]
    SIZE[n1] = 0

Z = N * (N - 1) // 2

ans = []
for i in range(M):
    a, b = A[i], B[i]
    unite(a, b)
    # print(PARENT[1:])
    # print(SIZE[1:])
    # print(g)
    # print(Z - g)
    ans.append(Z - g)
    # print("----")

ans.reverse()
del ans[0]
for a in ans:
    print(a)
print(Z)