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

A, B, M = map(int, input().split())
a_price = list(map(int, input().split()))
b_price = list(map(int, input().split()))
coupon = [list(map(int, input().split())) for i in range(M)]
min = a_price[0] + b_price[0]
for i in a_price:
    for j in b_price:
        if min > i+j:
            min = i+j

for cpn in coupon:
    idx_a = cpn[0]-1
    idx_b = cpn[1]-1
    total = a_price[idx_a] + b_price[idx_b] - cpn[2]
    if min > total:
        min = total

print(min)


### FIXED CODE ###

A, B, M = map(int, input().split())
a_price = list(map(int, input().split()))
b_price = list(map(int, input().split()))
coupon = [list(map(int, input().split())) for i in range(M)]



min = min(a_price) + min(b_price)


for cpn in coupon:
    idx_a = cpn[0]-1
    idx_b = cpn[1]-1
    total = a_price[idx_a] + b_price[idx_b] - cpn[2]
    if min > total:
        min = total

print(min)
### BUGGY CODE ###

import math
import bisect
import heapq
from collections import deque

def main():
    n, k = map(int, input().split())

    h = list(map(int, input().split()))
    inf = 10**7
    d = [inf] * n
    d[0] = 0

    for j in range(1, n):
        p = [d[i] + abs(h[j] - h[i]) for i in range(max(0, j - k), j)]

        d[j] = min(p)

    print(d[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

# import math
# import bisect
# import heapq
# from collections import deque

def main():
    n, k = map(int, input().split())

    h = list(map(int, input().split()))
    inf = 10**7
    d = [inf] * n
    d[0] = 0

    for j in range(1, n):
        p = [d[i] + abs(h[j] - h[i]) for i in range(max(0, j - k), j)]

        d[j] = min(p)

    print(d[-1])

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

m=int(input())
a=list(map(int,input().split()))
D=1
n=1

while n < m:
 if a[n] < max(a[0:n]):
  D=D
 else:
  D=D+1

print(D)

### FIXED CODE ###

m=int(input())
a=list(map(int,input().split()))
D=1
n=1

while n < m:
 if a[n] < max(a[0:n]):
  D=D 
  n=n+1
 else:
  D=D+1 
  n=n+1

print(D)
### BUGGY CODE ###

inf=float("inf")  


h,w=map(int,input().split())
s=[["#"]*(w+2) for i in range(h+2)]
for i in range(h):
    s[i+1]=["#"]+list(input())+["#"]

#h,w=3,5
#s=[['#', '#', '#', '#', '#', '#', '#'], ['#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#'], ['#', '#', '#', '#', '#', '#', '#']]    

nv=h*w
dp=[[inf]*nv for i in range(nv)] 

def nhw(hi,wi):
    return (hi-1)*w+wi-1

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        vij=nhw(i,j)
        if s[i-1][j]==".":
            vij2=nhw(i-1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i+1][j]==".":
            vij2=nhw(i+1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j-1]==".":
            vij2=nhw(i,j-1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j+1]==".":
            vij2=nhw(i,j+1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
for i in range(nv):
    dp[i][i]=0
           
#print(dp)
for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
#    print(dp)
#print(dp)
dpmax=0
for i in range(nv):
    for j in range(nv):
        if dp[i][j]!=inf:
            if dpmax<dp[i][j]:
                dpmax=dp[i][j]
print(dpmax)

### FIXED CODE ###

inf=float("inf")  


h,w=map(int,input().split())
s=[["#"]*(w+2) for i in range(h+2)]
for i in range(h):
    s[i+1]=["#"]+list(input())+["#"]

#h,w=3,5
#s=[['#', '#', '#', '#', '#', '#', '#'], ['#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#'], ['#', '#', '#', '#', '#', '#', '#']]    

nv=h*w
dp=[[inf]*nv for i in range(nv)] 

def nhw(hi,wi):
    return (hi-1)*w+wi-1

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        vij=nhw(i,j)
        if s[i-1][j]==".":
            vij2=nhw(i-1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i+1][j]==".":
            vij2=nhw(i+1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j-1]==".":
            vij2=nhw(i,j-1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j+1]==".":
            vij2=nhw(i,j+1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
for i in range(nv):
    dp[i][i]=0
           
#print(dp)
for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
#    print(dp)
#print(dp)
dpmax=0
for i in range(nv):
    for j in range(nv):
        if dp[i][j]!=inf:
            if dpmax<dp[i][j]:
                dpmax=dp[i][j]
print(dpmax)
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
r = 0

for i in range(0, n-1):
    s = 0
    for j in range(i+1, n):
        if h[j] > h[j-1]:
            break
        else:
            s = s+1
    if r < s:
        r = s

print(r)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
r = []
s = 0

for i in range(1, n):
    if h[i-1] >= h[i]:
        s = s + 1
    else:
        r.append(s)
        s = 0
        
r.append(s)

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

N, M = map(int, input().split())
E1 = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E1[a-1].append((b-1, -c))
    E2[b-1].append((a-1, -c))

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    k = 0
    while f:
        f = 0
        for i in range(n):
            for j, c in E[i]:
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
                    if k == N-1 and j == N-1: return (1, [])
        k += 1
    return (0, D)

b, d = bellman_ford(N, E1)
if b:
    print("inf")
else:
    print(-d[-1])


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
E1 = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E1[a-1].append((b-1, -c))
    E2[b-1].append((a-1, -c))

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c, w in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    while f:
        f = 0
        for i in range(n):
            if not B[i]: continue
            for j, c in E[i]:
                if not B[j]: continue
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
    return D

def bellman_ford_check(n, E, s=0):
    D = [0] * n
    for k in range(n):
        for i in range(n):
            if not B[i]: continue
            for j, c in E[i]:
                if not B[j]: continue
                if D[j] > D[i] + c:
                    D[j] = D[i] + c
                    if k == n-1: return 1
    return 0

B1 = BFS(N, E1, 0)
B2 = BFS(N, E2, N-1)
B = [0 if B1[i] < 0 or B2[i] < 0 else 1 for i in range(N)]

if bellman_ford_check(N, E1):
    print("inf")
else:
    D = bellman_ford(N, E1)
    print(-D[-1])
### BUGGY CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

import bisect

n = I()
a = LI()
a.sort()
q = I()
val = sum(a)
for i in range(q):
    b,c = LI()
    l = bisect.bisect_left(a,b)
    r = bisect.bisect_right(a,b)
    val += (c-b)*(r-l)
    for j in range(l,r):
        a[j] = c
    a.sort()
    print(val)

### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

import bisect

n = I()
a = LI()
q = I()

cnt = [0]*1000000
for i in a:
    cnt[i] += 1
sm = sum(a)

for i in range(q):
    b,c = LI()
    sm += (c-b)*cnt[b]
    if(c != b):
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(sm)
### BUGGY CODE ###

mod = 10**9+7
from fractions import gcd
def lcm(list):
    num = 1
    for x in list:
        num = num//gcd(num, x)*x
    return num

def Pow(a,n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

N = int(input())
A = list(map(int, input().split()))
M = lcm(A)
R = [0]*N
for i in range(N):
    R[i] = Pow(A[i],mod-2)
ans = 0
for i in range(N):
    ans = (ans+M*R[i])%mod
print(ans)

### FIXED CODE ###

mod = 10**9+7
from fractions import gcd
def lcm(list):
    num = 1
    for x in list:
        num = num//gcd(num, x)*x
    return num%mod

def Pow(a,n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

N = int(input())
A = list(map(int, input().split()))
M = lcm(A)
R = [0]*N
for i in range(N):
    R[i] = Pow(A[i],mod-2)
ans = 0
for i in range(N):
    ans = (ans+M*R[i])%mod
print(ans)
### BUGGY CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
gcd=math.gcd
def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

n = ni()
A = lma()
d=collections.Counter()
for i in range(n):
    a = A[i]
    fct = factorize(a)
    for fc,cnt in fct:
        if fc==1:continue
        d[fc]+=1

f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
if f2==False:
    print("not coprime")
    exit()
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
gcd=math.gcd

def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+2):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes
def factorize(n,primes):
    fct = [(1,1)]
    for b in primes:#primes ::sorted
        if b**2 > n:
            break
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= 10**6+10
prms = is_primes(mx)
prms2=[i for i in range(mx) if prms[i]]
#print(prms2)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #print(fct)
    for fc,cnt in fct:
        if fc==1:continue
        d[fc]+=1

f1=True # pp or sp
f2=True # sp or not p
for num,cnt in d.items():
    if cnt==n:
        f2=False #numが全体で共通の約数になる not coprime
        break
    else:
        if cnt==1:## 素
            pass
        else:
            f1=False

if f2==False:
    print("not coprime")
elif f1:
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

import collections
N=int(input())
a=[]
A=list(map(int,input().split()))
c=collections.Counter(A)
d=c.most_common()
Ans=[]
for i in range(N):
    ans=0
    if i>0:
        for l in range(i):
            if A[i]==A[l]:
                ans=Ans[l]
                break
    if ans==0:
        for j in range(len(d)):
            if d[j][0]==A[i]:
                ans+=(d[j][1]-1)*(d[j][1]-2)//2
            else:
                ans+=d[j][1]*(d[j][1]-1)//2
    Ans.append(ans)
for i in range(N):
    print(Ans[i])

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
ans=0
for i in c:
    ans+=c[i]*(c[i]-1)//2
for i in range(N):
    a=A[i]
    Ans=ans-c[a]+1
    print(Ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
 
def cmb(n,r):
    if r ==0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

inf = input().split()
N = int(inf[0])
K = int(inf[1])
M = N-K
for i in range(1,K+1):
  red = cmb(M+1,i)
  blue = cmb(K-1,i-1)
  print(red*blue%(10**9+7))

### FIXED CODE ###

from operator import mul
from functools import reduce
 
def cmb(n,r):
    r = min(n-r,r)
    if r==0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

inf = input().split()
N = int(inf[0])
K = int(inf[1])
M = N-K
for i in range(1,K+1):
  if M+1<i:
    red = 0
  else:
    red = cmb(M+1,i)
  blue = cmb(K-1,i-1)
  print(red*blue%(10**9+7))
### BUGGY CODE ###

def f():
    import sys
    input = sys.stdin.readline
    n,q=[int(j) for j in input().split()]
    l=[]
    for i in range(n):
        s,t,x=[int(j) for j in input().split()]
        l.append((s-x,1,x))
        l.append((t-x,0,x))

    for i in range(q):
        d=int(input())
        l.append((d,2,i))

    l.sort()

    ans=[-1]*q
    ll=set()
    m=10**18
    p=False
    for i,j,x in l:
        if j==1:
            ll.add(x)
            if m>x:
                m=x
                p=True
        elif j==0:
            ll.remove(x)
            if x==m:
                p=False
        else:
            if not p:
                if ll:
                    p=True
                    m=min(ll)
                else:
                    m=-1
            ans[x]=m
    print('\n'.join(map(str,ans)))

f()

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=[int(j) for j in input().split()]
l=[]
for i in range(n):
    s,t,x=[int(j) for j in input().split()]
    l.append((s-x,1,x))
    l.append((t-x,0,x))

for i in range(q):
    d=int(input())
    l.append((d,2,i))

l.sort()

ans=[-1]*q
ll=set()
m=10**18
p=False
for i,j,x in l:
    if j==1:
        ll.add(x)
        if m>x:
            m=x
            p=True
    elif j==0:
        ll.remove(x)
        if x==m:
            p=False
    else:
        if not p:
            if ll:
                p=True
                m=min(ll)
            else:
                m=-1
        ans[x]=m
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

a=int(input())
b=[i for i in range(a)]
c=int(sum(b))
print(c)

### FIXED CODE ###

a=int(input())
b=int(a*(a-1)//2)
print(b)
### BUGGY CODE ###

import functools
import numpy as np

n, X = map(int, input().split())
x = list(map(int, input().split()))

x.append(X)
x = np.array(x)
min_x = np.array([min(x) for _ in range(n+1)])
x = (sorted(x) - min_x)[1:]


def gcd(nums):
    return functools.reduce(euclid, nums)


def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)


print(gcd(x))


### FIXED CODE ###

import functools
import numpy as np

n, X = map(int, input().split())
x = list(map(int, input().split()))


def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)


if n > 1:
    if abs(x[0]-X) == 0:
        ans = euclid(abs(x[1]-X), abs(x[2]-X))
    elif abs(x[1]-X) == 0:
        ans = euclid(abs(x[0]-X), abs(x[2]-X))
    else:
        ans = euclid(abs(x[0]-X), abs(x[1]-X))

    for xi in x[2:]:
        ans = euclid(ans, abs(xi-X))
        if ans == 1:
            break

else:
    ans = abs(x[0] - X)

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

lst = list(map(int, input().split()))
N = lst.pop(3)
lst.sort(reverse=True)
R,G,B = lst
sum = 0
for i in range(int(N / R) + 1):
  for j in range(int((N - (i * R)) / G) + 1):
    for k in range(int((N - (i * R) - (j * G)) / B) + 1):
      ans = i * R + j * G + k * B
      if (ans == N):
        sum += 1
print(sum)

### FIXED CODE ###

R,G,B,N = map(int, input().split())

sum = 0
for i in range(N // R + 1):
  for j in range(N // G + 1):
    b = N - (i * R) - (j * G)
    if (b >= 0 and b % B == 0):
      sum += 1
print(sum)
### BUGGY CODE ###

x = int(input())
l = []
for i in range(2,x):
    key = "T"
    for j in l:
        if i % j == 0:
            key = "F"
            break
    if key == "T":
        l.append(i)
key = "F"
while key == "F":
    key1 = "T"
    for i in l:
        if x % i == 0:
            key1 = "F"
            break
    if key1 == "T":
        key = "T"
    x += 1
print(x-1)

### FIXED CODE ###

x = int(input())
l = []
for i in range(2,x):
    key = "T"
    for j in l:
        if i % j == 0:
            key = "F"
            break
    if key == "T":
        l.append(i)
key = "F"
while key == "F":
    key1 = "T"
    for i in l:
        if x % i == 0:
            key1 = "F"
            break
    if key1 == "T":
        key = "T"
    x += 1
print(x-1)
### BUGGY CODE ###

def solve(N, M, lrd):
    vs = {}
    def calc(l, r):
        cs = set([l])
        xs = [(l, 0)]
        while xs:
            x = xs.pop()
            if x[0] in vs:
                for y, d in vs[x[0]].items():
                    if y == r:
                        return d + x[1]
                    if y not in cs: 
                        xs.append((y, d + x[1]))
                        cs.add(y)
        return None
    for l, r, d in lrd:
        x = calc(l, r)
        if x is None:
            if l not in vs:
                vs[l] = {}
            if r not in vs:
                vs[r] = {}
            vs[l][r] = d
            vs[r][l] = -d
        elif x != d:
            return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

def solve(N, M, lrd):
    edges = {}
    nodes = {}
    for l, r, d in lrd:
        if not l in edges:
            edges[l] = {}
        if not r in edges:
            edges[r] = {}
        edges[l][r] = d
        edges[r][l] = -d
        nodes[l] = None
        nodes[r] = None
    for node in nodes:
        if nodes[node] is not None:
            continue
        nodes[node] = 0
        stack = []
        stack.append(node)
        while stack:
            node = stack.pop()
            for n, d in edges[node].items():
                if nodes[n] is None:
                    stack.append(n)
                    nodes[n] = nodes[node] + edges[node][n]
                else:
                    if nodes[n] != nodes[node] + edges[node][n]:
                        return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

S=input()
ans=len(S)
def solve(s):
    res=""
    cnt=0
    while cnt < len(s):
        if cnt == len(s)-1:
            res+=s[cnt]
            cnt+=1
        elif s[cnt] ==s[cnt+1]:
            res +=s[cnt]
            cnt+=1
        else:
            cnt+=2

    if len(s) == len(res):
        return ans-len(s)
    else:
        return solve(res)

print(solve(S))

### FIXED CODE ###

S=input()

cnt=0
for i in range(len(S)):
    if S[i]=="0":
        cnt+=1
    else:
        cnt-=1
print(len(S)-abs(cnt))
### BUGGY CODE ###

import numpy as np
number = np.arange(10**5+1)
primes = np.ones(10**5+1)

for i in range(10**3):
  if i <= 1:
    primes[i] = 0
    continue
  if primes[i] == 1:
    primes[number%i==0]=0
    primes[i] = 1
    
N = int(input())
for i in range(N):
  s, e = list(map(int, input().split()))
  res = 0
  for j in range(s, e+1):
    if primes[j] == 1 and primes[int((j+1)/2)]:
      res += 1
  print(res)    

### FIXED CODE ###

import numpy as np
number = np.arange(10**5+1)
primes = np.ones(10**5+1)
 
for i in range(int(np.sqrt(10**5+1))):
  if i <= 1:
    primes[i] = 0
    continue
  if primes[i] == 1:
    primes[number%i==0]=0
    primes[i] = 1
    
c = np.zeros(10**5+1)
for j in range(1, 10**5+1):
  if primes[j] == 1 and primes[int((j+1)/2)] == 1:
    c[j] = c[j-1] + 1
  else:
    c[j] = c[j-1]

N = int(input())
for i in range(N):
  s, e = list(map(int, input().split()))
  print(int(c[e]-c[s-1]))
### BUGGY CODE ###

n = int(input())
t = [0]+[int(i) for i in input().split()]+[0]
v = [int(i) for i in input().split()]+[0]
def f(x,v,t1,t2):
	if x<t1: return v+(t1-x)
	elif t1<=x<=t2: return v
	else: return v+(x-t2)
for i in range(1,n+2): t[i]+=t[i-1]
T,ans = 2*t[-1]+1,0
for i in range(T):
	num = i/2
	for j in range(n+1): num = min(num,f(i/2,v[j],t[j],t[j+1]))
	ans+=num/2
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
t = [0]+[int(i) for i in input().split()]+[0]
v = [int(i) for i in input().split()]+[0]
def f(x,v,t1,t2):
	if x<t1: return v+(t1-x)
	elif t1<=x<=t2: return v
	else: return v+(x-t2)
for i in range(1,n+2): t[i]+=t[i-1]
T,ans = t[-1],0
for i in range(2*T+1):
	num = min(i/2,T-i/2)
	for j in range(max(0,bisect_left(t,i/2-100)-1),n+1):
		if i/2<t[j]-100: break
		num = min(num,f(i/2,v[j],t[j],t[j+1]))
	ans+=num/2
print(ans)