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



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [10**12+1]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [10**12+1]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


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

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

def dfs(c):
  if len(c) == 0:
    return []

  for i in range(1, len(c)+1):
    if c[i-1] > i:
      return False

    if c[i-1] == i:
      cc = c.copy()
      del cc[i-1]
      res = dfs(cc)
      if res is not False:
        res.append(i)
        return res

  return False

res = dfs(b)
if res is False:
  print(-1)
else:
  for i in res:
    print(i)

### FIXED CODE ###

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

def dfs(c):
  if len(c) == 0:
    return []

  for i in range(len(c), 0, -1):
    if c[i-1] > i:
      return False

    if c[i-1] == i:
      cc = c.copy()
      del cc[i-1]
      res = dfs(cc)
      if res is not False:
        res.append(i)
        return res

  return False

res = dfs(b)
if res is False:
  print(-1)
else:
  for i in res:
    print(i)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
K = list(map(int,input().split()))

for i in range(q):
    ans = 0
    k = K[i]
    D = [[0] * 3 for j in range(n)]
    for j in range(n):
        D[j][:] = D[j-1][:]

        if j-k >= 0:
            if s[j-k] == "D":
                D[j][0] -= 1
                D[j][2] -= D[j][1]
            elif s[j-k] == "M":
                D[j][1] -= 1

        if s[j] == "D":
            D[j][0] += 1
        elif s[j] == "M":
            D[j][1] += 1
            D[j][2] += D[j][0]
        elif s[j] == "C":
            ans += D[j][2]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))
    # print(s)

    for i in range(q):
        ans = 0
        d = 0
        m = 0
        dm = 0
        k = K[i]
        for j in range(n):

            if j-k >= 0:
                if s[j-k] == "D":
                    d -= 1
                    dm -= m
                elif s[j-k] == "M":
                    m -= 1

            if s[j] == "D":
                d += 1
            elif s[j] == "M":
                m += 1
                dm += d
            elif s[j] == "C":
                ans += dm
        print(ans)

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

# -*- coding: utf-8 -*-

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

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


K = int(input())

def func_gcd(a, b):
    if b > a:
        a, b = b, a
    
    while b > 0:
        r = a % b
        a = b
        b = r

    return a

ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for l in range(1, K + 1):
            temp = func_gcd(i, j)
            temp2= func_gcd(temp, l)
            ans += temp2

print(ans)

### FIXED CODE ###

from math import gcd
 
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            ans += gcd(i, gcd(j,m))
print(ans)
### BUGGY CODE ###

def main():

    import sys
    from collections import defaultdict
    d = defaultdict(int)
    input = sys.stdin.readline

    n = int(input())
    polls = [input() for i in range(n)]

    for i in polls:
        d[i] += 1

    max_k_list = sorted([kv[0] for kv in d.items() if kv[1] == max(d.values())])

    for ans in max_k_list:
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

n = int(input())
polls = [input() for i in range(n)]

c = collections.Counter(polls)
maxval = c.most_common()[0][1]

values, counts = zip(*c.most_common())

ans = []

for i in c.most_common():
    if i[1] == maxval:
        ans.append(i[0])
    else:
        break

ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

# PyPyだとなぜか1ケースだけTLEする。Pythonでは通る。

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**5 + 5)  # 再帰回数の上限！！

n = int(input())
A = [int(input()) - 1 for i in range(n-1)]

M = [[] for i in range(n)]
for i in range(n-1):
    M[A[i]].append(i+1)

# 0-indexedの場合
V = [0] * n

# print(M)

def des(x):
    D = [0] * len(M[x])
    V[x] = 1
    for ii in range(len(M[x])):
        i = M[x][ii]
        if V[i] == 0:
            V[i] = 1
            D[ii] = des(i)
    if len(D) > 1:
        D.sort(reverse=True)
    # print(x,D)
    ans = 0
    for i in range(len(D)):
        D[i] += i+1
        ans = max(ans, D[i])
    return ans

print(des(0))

### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**5 + 5)  # 再帰回数の上限！！

n = int(input())
A = [-1] + [int(input()) - 1 for i in range(n-1)]

M = [[] for i in range(n)]
for i in range(1, n):
    M[A[i]].append(i)

# 0-indexedの場合
V = [0] * n

# print(M)

def des(x):
    D = []
    V[x] = 1
    for i in M[x]:
        if V[i] == 0:
            V[i] = 1
            D.append(des(i))
    D.sort(reverse=True)
    # print(x,D)
    for i in range(len(D)):
        D[i] += i+1
    if len(D) == 0:
        ans = 0
    else:
        ans = max(D)
    return ans

print(des(0))
### BUGGY CODE ###

def main():

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

    c = [0]*4
    for aa in a:
        c[aa] += 1

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

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

import numpy as np

x = np.zeros(100_001, dtype=int)
v = np.arange(100_001)

n = int(input())
for a in map(int, input().split()):
  x[a] += 1
q = int(input())
for _ in range(q):
  b, c = map(int, input().split())
  x[c] += x[b]
  x[b] = 0
  print(x @ v)

### FIXED CODE ###

x = [0] * 100_001
value = 0

n = int(input())
for a in map(int, input().split()):
  x[a] += 1
  value += a
q = int(input())
for _ in range(q):
  b, c = map(int, input().split())
  value += (c - b) * x[b]
  x[c] += x[b]
  x[b] = 0
  print(value)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    n, s = map(int, input().split())
    a = [int(x) for x in input().split()]
    mod = 998244353
    
    dp = [dict() for _ in range(s+1)]
    
    judge = dict()
    for i in range(n):
        for j in range(s-1, -1, -1):
            if dp[j] != judge:
                if a[i]+j <= s:
                    for k, v in dp[j].items():
                        if k+1 in dp[a[i]+j]:
                            key = (v+dp[a[i]+j][k+1])%mod
                            dp[a[i]+j][k+1] = key
                        else:
                            dp[a[i]+j][k+1] = v
            if j == 0:
                if a[i] <= s:
                    if 1 in dp[a[i]]:
                        key = (dp[a[i]][1]+1)%mod
                        dp[a[i]][1] = key 
                    else:
                        dp[a[i]][1] = 1
    
    ans = 0
    count = 1
    for k in range(n, 0, -1):
        if k in dp[s]:
            ans += (count*dp[s][k])%mod
            ans %= mod
        count *= 2
        count %= mod
    
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  n, s = map(int, input().split())
  a = [int(x) for x in input().split()]
  mod = 998244353
  
  dp = [[0]*(s+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i in range(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= mod

  print(dp[n][s])
  
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


def gcd_ab(a,b):
  while a != b:
    if a > b:
      a,b = [b,a]
    if a == 0:
      return b
    b = b-a
  return a


if __name__ == "__main__": 
  N = int(input())
  An = list(map(int, sys.stdin.readline().rstrip().split()))
  cum = [[0,0] for i in range(N+2)]

  for i in range(N):
    cum[i+1][0] = gcd_ab(cum[i][0], An[i])
    cum[N-i][1] = gcd_ab(cum[N-i+1][1], An[N-i-1])

  ans = [0 for i in range(N)]
  for i in range(1,N+1):
    ans[i-1] = gcd_ab(cum[i-1][0], cum[i+1][1])
  print(max(ans))


### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


def gcd_ab(a,b):
  a,b = sorted([a,b])
  if a == 0:
    return b
  return gcd_ab(b%a, a)

if __name__ == "__main__": 
  N = int(input())
  An = list(map(int, sys.stdin.readline().rstrip().split()))
  cum = [[0,0] for i in range(N+2)]

  for i in range(N):
    cum[i+1][0] = gcd_ab(cum[i][0], An[i])
    cum[N-i][1] = gcd_ab(cum[N-i+1][1], An[N-i-1])

  ans = [0 for i in range(N)]
  for i in range(1,N+1):
    ans[i-1] = gcd_ab(cum[i-1][0], cum[i+1][1])
  print(max(ans))
### BUGGY CODE ###

d,g = map(int,input().split())
li = [list(map(int,input().split())) for i in range(d)]

for i in range(d):
  li[i].append(li[i][0]*100*(i+1) + li[i][1])
tmp = 10 ** 9
def func(x,lis,cnt):
  global tmp
  if x <= 0:
    return cnt
  else:
    for i in range(d):
      if i in lis:
        continue
      else:
        if x <= 100*(i+1)*(li[i][0]-1):
          tmp = min(tmp,cnt + (x-1)//(100*(i+1)) + 1)
          #print("{} {} {}".format(i,lis,tmp))
        elif x <= li[i][2]:
          tmp = min(tmp,cnt + li[i][0])
          #print("{} {} {}".format(i,lis,tmp))
        else:
          tmp = min(tmp,func(x-li[i][2],lis+[i],cnt+li[i][0]))
          #print("{} {} {}".format(i,lis,tmp))
    return tmp
print(func(g,[],0))

### FIXED CODE ###

d,g = map(int,input().split())
li = [list(map(int,input().split())) for i in range(d)]

ans = 10 ** 9
for i in range(2**d):
  ch = bin(i)[2:]
  ch = ch.zfill(d)
  tmpsum = 0
  cnt = 0
  for j in range(d):
    if ch[j] == "1":
      tmpsum += li[j][0]*100*(j+1) + li[j][1]
      cnt += li[j][0]
  if tmpsum >= g:
    ans = min(ans,cnt)
    #print("{} {}".format(bin(i),cnt))
  else:
    ind = ch.rfind("0")
    if tmpsum + (li[ind][0]-1)*100*(ind+1) >= g:
      ans = min(ans,cnt+(g-tmpsum-1)//(100*(ind+1))+1)
      #print("{} {} {}".format(bin(i),cnt,ans))
print(ans)
### BUGGY CODE ###

import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
  # print(lis)
num = [0 for i in range(10 ** 6+5)]
ans = 0
for i in range(n):
    key = 1
    number = lis[i]
    if i > 0:
        if lis[i] == lis[i-1]:
            key = 0
    if i < n-1:
        if lis[i] == lis[i+1]:
            key = 0
    for i in range(1,math.ceil(math.sqrt(number))+1):
        if number % i == 0:
            a = number//i
            b = i
            if num[a] != 0 or num[b] != 0:
                key = 0
    if key == 1:
        ans += 1
    num[number] = 1
print(ans)

### FIXED CODE ###

import math
n = int(input())
lis = list(map(int,input().split()))
ans = 0
num = [1 for i in range(10 ** 6 + 5)]
lis.sort()
for i in range(n):
  #     print(lis[i])
    key = 1
    gone = 1
    if i > 0:
        if lis[i] == lis[i-1]:
            key = 0
            gone = 0
    if i < n-1:
        if lis[i] == lis[i+1]:
            key = 0
    ans += num[lis[i]] * key
    num[lis[i]] = 0
    cnt = lis[i]
    t = 1
    if gone:
        while cnt*t <= 10 ** 6:
            num[cnt*t] = 0
            t += 1
print(ans)
### BUGGY CODE ###

from scipy.special import comb
import bisect

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

# N=2の時は組み合わせは1つしかない
if N == 2:
    print(A[0], A[1])
    exit(0)


A.sort()
n = A[-1]

# 二分探査で最大値を求める
r = 0
mid_idx = N//2
while True:
    mid_comb = comb(n, A[mid_idx], exact=True)
    mid_h_comb = comb(n, A[mid_idx+1], exact=True)
    mid_l_comb = comb(n, A[mid_idx-1], exact=True)

    # 初期値の真ん中が答えだった場合
    if mid_comb == max(mid_comb, mid_h_comb, mid_l_comb):
        r = A[mid_idx]
        break

    # 次の中央値を求める
    if mid_comb < mid_h_comb:
        mid_idx = (mid_idx+N)//2
    else:
        mid_idx = mid_idx//2

print(n, r)


### FIXED CODE ###

import bisect

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

A.sort()
n = A[-1]
mid = bisect.bisect(A, n/2)

if abs(n/2-A[mid-1]) > abs(n/2-A[mid]):
    print(n, A[mid])
else:
    print(n, A[mid-1])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                tot += n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                tot += sr
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

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

N, P = map(int, input().split())

from math import sqrt
from collections import Counter

def is_prime(n):
    if n == 1: return False
    if n == 2: return True
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0: return False
    return True

def prime_factorization(n):
    #if is_prime(n):return [n]
    factor = []
    f = 2
    while n > 1:
        if n % f == 0:
            factor.append(f)
            n /= f
        else:
            f += 1
    return factor

p = prime_factorization(P)
c = Counter(p)

l = []
j = []
for k, v in c.items():
    if N <= v:
        l.append(k)
        j.append(v//N)
ans = 1
for i,v in zip(l,j):
    ans *= i**v

print(ans)

### FIXED CODE ###

from collections import Counter

N, P = map(int, input().split())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(P)
c = Counter(p)

l = []
j = []
for k, v in c.items():
    if N <= v:
        l.append(k)
        j.append(v//N)
ans = 1

for i,v in zip(l,j):
    ans *= i**v

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    # n!/(n-k)!
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    # k!
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    # n!/((n-k)!*k!)
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])

    mod = 10**9+7

    cmb = [0] * N
    for i in range(N):
        cmb[i] = getComb(i,K-2,mod)

    answer = 0
    for i in range(N):
        for j in range(i+(K-1), N):
            answer = (answer + cmb[j-i-1] * ((A[j] - A[i]) % mod)) % mod

    print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def getComb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


N,K = map(int,input().split())
A = sorted([int(i) for i in input().split()])

# ref: https://www.planeta.tokyo/entry/5195/
mod = 10**9+7
fact = [1, 1]
factinv = [1, 1] 
inv = [0, 1]
for i in range(2,N+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

cmb = [0] * (N-K+1)
for i in range(N-K+1):
    cmb[i] = getComb(i+(K-1),K-1,mod)

sum_max = 0
for i in range(K-1,N):
    sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod

sum_min = 0
for i in range(N-K,-1,-1):
    sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod

answer = sum_max - sum_min
print(answer % mod)
### BUGGY CODE ###

N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)

### FIXED CODE ###

N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)