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

li = input().split()
n = int(li[0])
m = int(li[1])
# IDカードn枚，　ゲートm個
l_r = []
# i番目のゲートはl~rのIDカードを持っていれば通過できる
l_r = [input().split() for i in range(m)]
answer = 0
for i in range(n):
    for lr in l_r:
        l = int(lr[0])
        r = int(lr[1])
        if l <= i + 1 and i + 1 <= r:
            continue
        else:
            break
    else:
        answer += 1
print(answer)

### FIXED CODE ###

li = input().split()
n = int(li[0])
m = int(li[1])
# IDカードn枚，　ゲートm個
# i番目のゲートはl~rのIDカードを持っていれば通過できる
l_r = [input().split() for i in range(m)]
l_r.sort(key=lambda x:int(x[0]))
l_max = int(l_r[-1][0])
l_r.sort(key=lambda x:int(x[1]))
r_min = int(l_r[0][1])
answer = 0
# for i in range(n):
#     if l_max <= i + 1 and i + 1 <= r_min:
#         answer += 1
diff = r_min - l_max + 1
if diff > 0:
    print(diff)
else:
    print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    def add(n, x, f):
        C[n] = x = C[n] + x
        for c in V[n]:
            if c != f:
                add(c, x, n)
    add(0, 0, 0)
    print(' '.join(str(c) for c in C))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    cur = [(0, 0)]
    while cur:
        nxt = []
        for n, x in cur:
            C[n] = x = C[n] + x
            for c in V[n]:
                V[c].remove(n)
                nxt.append((c, x))
        cur = nxt
    print(' '.join(str(c) for c in C))

main()
### BUGGY CODE ###

import copy

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

#print(S)
inf = 10 ** 3
data = [[[[inf for i in range(W+2)] for j in range(H+2)] for k in range(W+2)] for l in range(H+2)]

for i in range(1,H+1):
    for j in range(1,W+1):
        data[i][j][i][j] = 0

for m in range((H*W)//2):
    data_ = copy.copy(data)
    for i in range(1,H+1):
      for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if S[i][j] == "#" or S[k][l] == "#":
                    continue
                data_[i][j][k][l] = min(data[i][j][k][l],data[i][j][k+1][l]+1,data[i][j][k-1][l]+1,data[i][j][k][l+1]+1,data[i][j][k][l-1]+1)

x = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if x < data_[i][j][k][l] and data_[i][j][k][l] != inf:
                    x = data_[i][j][k][l]

print(x)


### FIXED CODE ###

#いい加減深さ優先探索, 幅優先探索をスムーズに実装してえなおい

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

inf = 10 ** 3
m = 0
mi = -1
mj = -1
mk = -1
ml = -1
  
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "#":
            continue
        data = [[inf]*(W+2) for k in range(H+2)]
        data[i][j] = 0
        stack = [[i,j,0]]
        while stack:
            x = stack.pop()
            if S[x[0]+1][x[1]] == "." and data[x[0]+1][x[1]]>x[2]+1:
                data[x[0]+1][x[1]] = x[2]+1
                stack.append([x[0]+1,x[1],x[2]+1])
            if S[x[0]][x[1]+1] == "." and data[x[0]][x[1]+1]>x[2]+1:
                data[x[0]][x[1]+1] = x[2]+1
                stack.append([x[0],x[1]+1,x[2]+1])
            if S[x[0]-1][x[1]] == "." and data[x[0]-1][x[1]]>x[2]+1:
                data[x[0]-1][x[1]] = x[2]+1
                stack.append([x[0]-1,x[1],x[2]+1])
            if S[x[0]][x[1]-1] == "." and data[x[0]][x[1]-1]>x[2]+1:
                data[x[0]][x[1]-1] = x[2]+1
                stack.append([x[0],x[1]-1,x[2]+1])
            #print(i,j,stack)

        for k in range(1,H+1):
            for l in range(1,W+1):
                if data[k][l] > m and data[k][l] != inf:
                    m = data[k][l]
                    mi = i
                    mj = j
                    mk = k
                    ml = l

#print(mi,mj,mk,ml)
print(m)

#DFSならワイの実装力でも割とスムーズにできそう？
#なんで昨日これやらなかったんや
#と言いつつWAするアホ
### BUGGY CODE ###

n, m = list(map(int, input().split()))
tmps = [[] for i in range(n)]
pys = []

for i in range(0, m):
    p, y = list(map(int, input().split()))
    tmps[p-1].append(y)
    pys.append([p, y])

for i in range(n):
    tmps[i].sort()

for py in pys:
    p, y = py
    yindex = tmps[p-1].index(y)+1
    print('{:06}'.format(p) + '{:06}'.format(yindex))

### FIXED CODE ###

n, m = list(map(int, input().split()))
tmps = [[] for _ in range(n)]
pyxs = []

for i in range(m):
    p, y = list(map(int, input().split()))
    pyxs.append([p, y, i])

pyxs.sort(key = lambda x: x[1])

num = [0] * (n+1)
ans = [None]*m

for p, y, x in pyxs:
    ans[x] = '{:06}'.format(p) + '{:06}'.format(num[p]+1)
    num[p] += 1

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

import sys

sys.setrecursionlimit(200000)

n = int(input())
 
def dp(i, a, b, c):
	if i == -1: return 0
	a_v = dp(i-1, a=False, b=True, c=True) + al[i] if a else -1
	b_v = dp(i-1, a=True, b=False, c=True) + bl[i] if b else -1
	c_v = dp(i-1, a=True, b=True, c=False) + cl[i] if c else -1
	return max([a_v, b_v, c_v])
 
al = []
bl = []
cl = []
for i in range(n):
	a, b, c = list(map(int, input().split(" ")))
	al.append(a)
	bl.append(b)
	cl.append(c)
    
print(dp(n-1, a=True, b=True, c=True))


### FIXED CODE ###

import sys

sys.setrecursionlimit(200000)

n = int(input())
 
m ={}
def dp(i, a, b, c):
	if (i,a,b,c) in m:
		return m[(i,a,b,c)]
	if i == -1: return 0
	a_v = dp(i-1, a=False, b=True, c=True) + al[i] if a else -1
	b_v = dp(i-1, a=True, b=False, c=True) + bl[i] if b else -1
	c_v = dp(i-1, a=True, b=True, c=False) + cl[i] if c else -1
	m[(i,a,b,c)] = max([a_v, b_v, c_v])
	return max([a_v, b_v, c_v])
 
al = []
bl = []
cl = []
for i in range(n):
	a, b, c = list(map(int, input().split(" ")))
	al.append(a)
	bl.append(b)
	cl.append(c)
    
print(dp(n-1, a=True, b=True, c=True))
### BUGGY CODE ###


def sum_dict(d):
    num = 0
    for k, v in d.items():
        num += k * v
    return num


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(tuple(map(int, input().split())))

    d = {}
    for a in A:
        if d.get(a) is None:
            d[a] = 1
        else:
            d[a] += 1

    for b, c in BC:
        db = d.get(b)
        if db is None:
            db = 0
        if d.get(c) is None:
            d[c] = 0
        d[c] += db
        d[b] = 0
        print(sum_dict(d))


### FIXED CODE ###


def sum_dict(d):
    num = 0
    for k, v in d.items():
        num += k * v
    return num


def create_dict(A):
    d = {}
    for a in A:
        if d.get(a) is None:
            d[a] = 1
        else:
            d[a] += 1
    return d


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(tuple(map(int, input().split())))

    d = create_dict(A)

    ans = sum_dict(d)
    for b, c in BC:
        db = d.get(b)
        if db is None:
            db = 0
        if d.get(c) is None:
            d[c] = 0
        d[c] += db
        d[b] = 0

        ans += (c - b) * db
        print(ans)
### BUGGY CODE ###

from itertools import accumulate

Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])


### FIXED CODE ###

import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
tmp=sys.maxsize
for i in range(n+1):
    if tmp > abs(sum(a[:i])-sum(a[i:])):
        tmp = abs(sum(a[:i])-sum(a[i:]))
    else:
        print(tmp)
        exit()

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
tmp=sys.maxsize
s = sum(a)
t = 0
for i in range(n):
    t += a[i]
    tmp = min(tmp,abs(s-t*2))
print(tmp)
### BUGGY CODE ###

text = input()
result=[0]*len(text)
letter=[]
for i in range(1,len(text)):
  if(text[i]!=text[i-1]):
    letter=letter+[i]
letter=letter+[len(text)]

##端の処理
i=0
while(text[i]=="L"):
  i=i+1
result[0]=i
i=0
while(text[-i-1]=="R"):
  i=i+1
result[-1]=i


####RRR...(n個)...RL...(m個)...Lのとき
####n+mが偶数なら(n+m)/2個ずつ
####奇数ならnが奇数のときRに(n+m+1)/2,Lに(n+m-1)/2
####nが偶数のときRに(n+m-1)/2,Lに(n+m+1)/2たまる

#はじめの文字がLのとき
if(text[0]=="L"):
  i=1
  while(i+1<len(letter)):
    n=letter[i]-letter[i-1]
    m=letter[i+1]-letter[i]
    if((n+m)%2==0):
      result[letter[i]-1]=(n+m)//2
      result[letter[i]]=(n+m)//2
    elif(n%2==1):
      result[letter[i]-1]=(n+m+1)//2
      result[letter[i]]=(n+m-1)//2   
    else:
      result[letter[i]-1]=(n+m-1)//2
      result[letter[i]]=(n+m+1)//2
    i=i+2
else:
  n=letter[0]
  m=letter[1]-letter[0]
  if((n+m)%2==0):
    result[letter[0]-1]=(n+m)//2
    result[letter[0]]=(n+m)//2
  elif(n%2==1):
    result[letter[0]-1]=(n+m+1)//2
    result[letter[0]]=(n+m-1)//2   
  else:
    result[letter[0]-1]=(n+m-1)//2
    result[letter[0]]=(n+m+1)//2 
  i=2
  while(i+1<len(letter)):
    n=letter[i]-letter[i-1]
    m=letter[i+1]-letter[i]
    if((n+m)%2==0):
      result[letter[i]-1]=(n+m)//2
      result[letter[i]]=(n+m)//2
    elif(n%2==1):
      result[letter[i]-1]=(n+m+1)//2
      result[letter[i]]=(n+m-1)//2   
    else:
      result[letter[i]-1]=(n+m-1)//2
      result[letter[i]]=(n+m+1)//2
    i=i+2
print(' '.join(map(str, result)))

### FIXED CODE ###

text = input()
result=[0]*len(text)
N=len(text)

####RRR...(n個)...RL...(m個)...Lのとき
####n+mが偶数なら(n+m)/2個ずつ
####奇数ならnが奇数のときRに(n+m+1)/2,Lに(n+m-1)/2
####nが偶数のときRに(n+m-1)/2,Lに(n+m+1)/2たまる

s=0
i=0
j=0
while j<N :
  while text[i]=="R" :
    i+=1
  j=i+1
  while (j<N and text[j]=="L") :
    j+=1
  if (j-s)%2==0:
    result[i-1]=(j-s)//2
    result[i]=(j-s)//2
  else:
    result[i-1]=(j-s-1)//2
    result[i]=(j-s-1)//2
    result[i-(s-i)%2]+=1
  s=j
  i=s+1

print(' '.join(map(str, result)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
p = 1
x = True

for i in a:
    p *= i
if p > (10 ** 18):
    x = False


if x == True:
    print(p)
else:
    print(-1)
        

### FIXED CODE ###

# 169 B

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

def code(a):
    pro = 1
    if 0 in a:
        print(0)
    else:
        for i in a:
            pro *= i
            if pro > (10 ** 18):
                print(-1)
                return
        print(pro)

code(l)
### BUGGY CODE ###

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

N, A, B = input().split() 
balls = []
bBalls = []
rBalls = []

for i in range(int(A)):
    rBalls.append("b")

for i in range(int(B)):
    rBalls.append("r")

answer = 0
isBreak = False
for i in range(10**100):
   balls = bBalls + rBalls + balls
   if( len(balls) > int(N) ) :
       for c in range(int(N)):
           if(balls[c] == "b") :
               answer = answer +1
               isBreak = True
       isBreak = True
   if( isBreak ) :
       break

print(answer)


### FIXED CODE ###

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

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

x = (N // (A + B)) * A 
mod = N % (A + B)
if mod <= A :
    z = mod
else :
    z = A

print(x + z)
### BUGGY CODE ###

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

import os
import sys

input()
nums = [int(i) for i in input().split()]
answer = 0

for i in range(len(nums)):
    for j in range(i, len(nums) + 1):
        if i == j:
            continue
        if sum(nums[i:j]) == 0:
            answer = answer + 1

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
import math

lenums = int(input())
nums = [int(i) for i in input().split()]
answer = 0

dp = [0]

for i in range(lenums):
    dp.append(dp[i] + nums[i])

count_dict = collections.Counter(dp)
for i in count_dict.values():
    if i <= 1:
        continue
    answer = answer + i * (i - 1) // 2 # xC2

print(answer)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
#print(l)
li=sorted(l)
#print(li)
for i in l:
    a=li.index(i)+1
    if i[0]>=2:
        for j in li:
            if i[0]==j[0]:
                b=li.index(j)
                a=a-b
                break
    print(str('%06d'%i[0])+str('%06d'%a))     

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=[]
for i in enumerate(l):
    s.append(i)
s=sorted(s,key=lambda x:(x[1][0],x[1][1]))
#print(s)
a=1
for i in range(m):
    if i==0:
        s[0][1][1]=1
    elif s[i][1][0]==s[i-1][1][0]:
        a+=1
        s[i][1][1]=a
    elif s[i][1][0]!=s[i-1][1][0]:
        a=1
        s[i][1][1]=a
#print(s)
s=sorted(s,key=lambda x:x[0])
#print(s)
for i in s:
    print('%06d'%i[1][0]+'%06d'%i[1][1])
### BUGGY CODE ###

import itertools
import math

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

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, n + 1):
        # fact[i] = ((fact[i-1] * i) % p)
        # inv[i] = ((-inv[p % i] * (p // i)) % p)
        # factinv[i] = ((factinv[i-1] * inv[i]) % p)
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)


    return fact[n] * factinv[r] * factinv[n-r] % p


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

print(ans%mod)

### FIXED CODE ###

# import itertools
# import math

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

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(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
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
    
for i in range(2, N + 1):
    # fact[i] = ((fact[i-1] * i) % p)
    # inv[i] = ((-inv[p % i] * (p // i)) % p)
    # factinv[i] = ((factinv[i-1] * inv[i]) % p)
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)




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

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

N = int(input())

def dividor(K):
    X = [0]*K
    num = K
    for i in range(2,num+1):
        while(num%i == 0):
            X[i-1] +=1
            num = num // i
    ans = 1
    for i in range(1,K):
        ans = ans * (X[i] + 1)
    return ans
sum = 1
for i in range(2,N+1):
    sum += i * dividor(i)
print(sum)

### FIXED CODE ###

N = int(input())
ans = 0
for j in range(1,N+1):
    Y = N//j
    ans += Y*(Y+1)*j//2
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

r,c,k=map(int,input().split())

item=[[0]*c for i in range(r)]
for i in range(k):
    R,C,v=map(int,input().split())
    item[R-1][C-1]=v

dp=[[[-10**10]*4 for i in range(c)] for j in range(r)]

if item[0][0]==0:
    dp[0][0][0]=0
else:
    dp[0][0][0]=0
    dp[0][0][1]=item[0][0]

for i in range(r):
    for j in range(c):
        if j!=c-1:
            v=item[i][j+1]
            if v==0:
                for k in range(4):
                    dp[i][j+1][k]=max(dp[i][j][k],dp[i][j+1][k])
            else:
                dp[i][j+1][0]=max(dp[i][j][0],dp[i][j+1][0])
                dp[i][j+1][1]=max(dp[i][j][0]+v,dp[i][j][1],dp[i][j+1][1])
                dp[i][j + 1][2] = max(dp[i][j][1] + v, dp[i][j][2], dp[i][j + 1][2])
                dp[i][j + 1][3] = max(dp[i][j][2] + v, dp[i][j][3], dp[i][j + 1][3])
        if i!=r-1:
            v=item[i+1][j]
            if v==0:
                dp[i+1][j][0]=max(dp[i][j][0],dp[i][j][1],dp[i][j][2],dp[i][j][3],dp[i+1][j][0])
            else:
                dp[i + 1][j][0] = max(dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3], dp[i + 1][j][0])
                dp[i + 1][j][1] = max(dp[i][j][0]+v, dp[i][j][1]+v, dp[i][j][2]+v, dp[i][j][3]+v, dp[i + 1][j][1])

ans=max(dp[r-1][c-1][0],dp[r-1][c-1][1],dp[r-1][c-1][2],dp[r-1][c-1][3])
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

    item=[[0]*c for i in range(r)]
    for i in range(k):
        R,C,v=map(int,input().split())
        item[R-1][C-1]=v

    dp0=[[-10**10]*c  for i in range(r)]
    dp1 = [[-10 ** 10] * c for i in range(r)]
    dp2 = [[-10 ** 10] * c for i in range(r)]
    dp3 = [[-10 ** 10] * c for i in range(r)]

    if item[0][0]==0:
        dp0[0][0]=0
    else:
        dp0[0][0]=0
        dp1[0][0]=item[0][0]

    for i in range(r):
        for j in range(c):
            if j!=c-1:
                v=item[i][j+1]
                if v==0:
                    dp0[i][j+1]=max(dp0[i][j],dp0[i][j+1])
                    dp1[i][j + 1] = max(dp1[i][j], dp1[i][j + 1])
                    dp2[i][j + 1] = max(dp2[i][j], dp2[i][j + 1])
                    dp3[i][j + 1] = max(dp3[i][j], dp3[i][j + 1])
                else:
                    dp0[i][j+1]=max(dp0[i][j],dp0[i][j+1])
                    dp1[i][j+1]=max(dp0[i][j]+v,dp1[i][j],dp1[i][j+1])
                    dp2[i][j + 1] = max(dp1[i][j] + v, dp2[i][j], dp2[i][j + 1])
                    dp3[i][j + 1] = max(dp2[i][j] + v, dp3[i][j], dp3[i][j + 1])
            if i!=r-1:
                v=item[i+1][j]
                if v==0:
                    dp0[i+1][j]=max(dp0[i][j],dp1[i][j],dp2[i][j],dp3[i][j],dp0[i+1][j])
                else:
                    dp0[i+1][j]=max(dp0[i][j],dp1[i][j],dp2[i][j],dp3[i][j],dp0[i+1][j])
                    dp1[i + 1][j] = max(dp0[i][j]+v, dp1[i][j]+v, dp2[i][j]+v, dp3[i][j]+v, dp1[i + 1][j])

    ans=max(dp0[r-1][c-1],dp1[r-1][c-1],dp2[r-1][c-1],dp3[r-1][c-1])
    print(ans)

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

num = int(input())
input_line = input().split()

num_list = [int(input_line[i]) for i in range(num)]
law = 10 ** 9 + 7
sigma = 0
for i in range(num):
  for j in range(i+1,num):
    num_a = num_list[i]
    num_b = num_list[j]
    
    sigma += num_a * num_b

sigma %= law
print(sigma)

### FIXED CODE ###

num = int(input())
input_line = input().split()

law = 10 ** 9 + 7
num_list = [int(input_line[i])%law for i in range(num)]

sigma = 0
temp_sum = 0
for j in range(num):
	temp_sum += num_list[j]

for i in range(num):
	num_a = num_list[i]
	temp_sum -= num_a
	sigma += num_a * temp_sum


sigma %= law
print(sigma)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N,K=map(int, input().split())
P = list(map(int, input().split()))

# 1+0.5(N-1)

print()

tmp = 0
start = 0
for i in range(N-K+1):
    if tmp < sum(P[i:i+K]):
        tmp = sum(P[i:i+K])
        start = i

ans = 0
for j in range(start,start+K):
    ans += (P[j]+1)/2

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N,K=map(int, input().split())
P = list(map(int, input().split()))

S = []

for i in range(N):
    S.append((P[i]+1)/2)

tmp = sum(S[:K])
ans = tmp

for i in range(N-K):
    tmp = tmp - S[i] + S[i+K]
    ans = max(ans, tmp)


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

N=int(input())
s=[]
for i in range(N):
	s.append(input())

for i in range(N):
	s[i]=sorted(s[i])

count=0
for i in range(N):
	for j in range(i+1,N):
		if s[i]==s[j]:
			count += 1
print(count)


### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

for i in range(N):
	S[i].sort()

for i in range(N):
	S[i] = "".join(S[i])

S.sort()
S.append(None)

pt,count,C = 1,0,[]
while pt <= N:
	if S[pt-1] == S[pt]:
		count += 1
	else:
		if count > 0:
			C.append(count+1)
			count = 0
	pt += 1

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

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

A,B = map(int, input().split())
xor = str(A)
for i in range(B-A):
    xor += ' ^ '+str(A+i+1)

print(eval(xor))

### FIXED CODE ###

def calc(a):
    val = int((a+1) / 2)
    ans = (val % 2) ^ a if a % 2 == 0 else val % 2
    return ans
A,B = map(int, input().split())

print(calc(A -1) ^ calc(B))
### BUGGY CODE ###

N = int(input())
P_list = list(map(int,input().split()))
M_list = []
cnt = 0
for j in range(1,N+1):
  M_list.append(min(P_list[:j]))

for i in range(N):
  if M_list[i] == P_list[i]:
    cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
P_list = list(map(int,input().split()))
M = P_list[0]
cnt = 1

for i in range(N):
  if M > P_list[i]:
    cnt += 1
    M = P_list[i]

print(cnt)