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

import numpy as np

N, K = map(int, input().split())
hs = np.array(list(map(int, input().split())))

i = 0
 
a = []
a.append(0)
a.append(abs(hs[1] - hs[0]))

for i in range(2, N):
    bmin = float('inf')
    for j in range(max(i-K,0),i):
        bmin = min(bmin, a[j] + abs(hs[i] - hs[j]))    
    a.append(bmin)
print(a[-1])


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
hs = np.array(list(map(int, input().split())))

i = 0
total_cost = 0
 
a = np.zeros(N, dtype=np.int64)
a[0] = 0
a[1] = abs(hs[1] - hs[0])

for i in range(2, N):
    k = min(K,i)
    a[i] = np.min(a[i-k:i] + np.abs(hs[i] - hs[i-k:i]))    
print(a[-1])
### BUGGY CODE ###

import collections as C
n, q = map(int,input().split())

g = C.Counter([])
p = C.Counter([])
for i in range(n-1):
	a,b = map(int,input().split())
	if a not in g.keys():
		g[a] = [b]
	elif a in g.keys():
		g[a].append(b)

for i in range(q):
	a,b = map(int,input().split())
	if a not in p.keys():
		p[a] = b
	elif a in p.keys():
		p[a] += b

ans = [0 for _ in range(n)]
que = [0]
i = 1
while i > 0:

	if i in p.keys():
		ans[i-1] += p[i]
	if i in g.keys():
		for j in g[i]:
			ans[j-1] = ans[i-1]
			que.append(j)
	i = que.pop()


for i in ans:
	print(i, end=" ")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N, Q = map(int ,input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
	at,bt = map(int ,input().split())
	E[at].append(bt)
	E[bt].append(at)
cnt = [0 for _ in range(N+1)]
for _ in range(Q):
	pt,xt = map(int, input().split())
	cnt[pt] += xt

flg = [0 for _ in range(N+1)]
q = [[1,-1]]
while q:
	cp, root = q.pop()
	for np in E[cp]:
		if np == root:
			continue
		cnt[np] += cnt[cp]
		q.append([np,cp])

cnt.pop(0)
for c in cnt:
	print(c, end = " ")
print()
### BUGGY CODE ###

S=input()
Q=int(input())
query=[input().split() for _ in range(Q)]

reverse=False
for q in query:
    if q[0]=="1":
        reverse = not reverse
    else:
        if q[1]=="1":
            if reverse:
                S=S+q[2]
            else:
                S=q[2]+S
        else:
            if reverse:
                S=q[2]+S
            else:
                S=S+q[2]
if reverse:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S=input()
Q=int(input())
query=[input().split() for _ in range(Q)]

reverse=False
lst=["" for _ in range(500000+10)]
sp=200000+5
fp=200000+5

for i in range(len(S)):
    lst[sp+i]=S[i]
    fp+=1

for q in query:
    if q[0]=="1":
        reverse = not reverse
    else:
        if q[1]=="1":
            if reverse:
                #S=S+q[2]
                lst[fp]=q[2]
                fp+=1
            else:
                #S=q[2]+S
                sp-=1
                lst[sp]=q[2]
        else:
            if reverse:
                #S=q[2]+S
                sp-=1
                lst[sp]=q[2]
            else:
                #S=S+q[2]
                lst[fp]=q[2]
                fp+=1

if reverse:
    #print(S[::-1])
    print("".join(lst[::-1]))
else:
    #print(S)
    print("".join(lst))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[0 for i in range(N)] for l in alphabet}

for i in range(N):
  bag[S[i]][i] = 1

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    bag[S[a-1]][a-1] = 0
    S[a-1] = b
    bag[b][a-1] = 1
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if sum(bag[l][a-1:b]) > 0:
        count += 1
    print(count)


### FIXED CODE ###

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    if S[a-1]!=b:
      bag[S[a-1]].remove(a)
      S[a-1] = b
      bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if len(bag[l])>0:
        left = bisect.bisect_left(bag[l],a)
        if left != len(bag[l]):
          if bag[l][left] <= b:
            count += 1
    print(count)
### BUGGY CODE ###

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

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
for node in range(n-2, -1, -1):
    routes = edges_from[node]
    num_of_routes = len(routes)
    for next_node in routes:
        dist = E_dist_to_goal[next_node] + 1
        E_dist_to_goal[node] += dist/num_of_routes


def recalculate_dist(node, E_dist_to_goal):
    recal_E_dist = [0]*(node+1)
    routes = edges_from[node]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        return False

    heaviest_route = max(E_dist_to_goal[next_node]+1 for next_node in routes)
    new_dist = E_dist_to_goal[node] - heaviest_route/num_of_routes
    new_dist *= num_of_routes / (num_of_routes - 1)
    recal_E_dist[node] = new_dist

    for v in range(node-1, -1, -1):
        routes = edges_from[v]
        num_of_routes = len(routes)
        for nv in routes:
            if nv > node:
                dist = E_dist_to_goal[nv] + 1
            else:
                dist = recal_E_dist[nv] + 1
            recal_E_dist[v] += dist
        recal_E_dist[v] /= num_of_routes
    return recal_E_dist[0]


ans = [E_dist_to_goal[0]]
for i in range(n-2):
    candidate = recalculate_dist(i, E_dist_to_goal)
    if candidate:
        ans.append(candidate)

print(min(ans))


### FIXED CODE ###

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

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
for node in range(n-2, -1, -1):
    routes = edges_from[node]
    num_of_routes = len(routes)
    for next_node in routes:
        dist = E_dist_to_goal[next_node] + 1
        E_dist_to_goal[node] += dist/num_of_routes


def recalculate_dist(node, E_dist_to_goal):
    recal_E_dist = [0]*(node+1)
    routes = edges_from[node]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        return False

    heaviest_route = max(E_dist_to_goal[next_node]+1 for next_node in routes)
    new_dist = E_dist_to_goal[node] - heaviest_route/num_of_routes
    new_dist *= num_of_routes / (num_of_routes - 1)
    recal_E_dist[node] = new_dist

    for v in range(node-1, -1, -1):
        routes = edges_from[v]
        num_of_routes = len(routes)
        for nv in routes:
            if nv > node:
                dist = E_dist_to_goal[nv] + 1
            else:
                dist = recal_E_dist[nv] + 1
            recal_E_dist[v] += dist
        recal_E_dist[v] /= num_of_routes
    return recal_E_dist[0]


ans = [E_dist_to_goal[0]]
for i in range(n-2):
    candidate = recalculate_dist(i, E_dist_to_goal)
    if candidate:
        ans.append(candidate)

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

import numpy as np
 
N,K=map(int, input().split())
P=np.array(list(map(int, input().split())))
 
ans=0
for i in range(N):
  try:
    ans=max(ans,sum(P[i:i+K]))
  except:
    break
print((ans+K)/2)

### FIXED CODE ###

import sys

N,K=map(int,input().split())
P=list(map(int,input().split()))
Q=[(1+p)/2 for p in P]
temp=sum(Q[:K])
ans=temp
for i in range(N):
  try:
    temp=temp-Q[i]+Q[i+K]
    ans=max(ans,temp)
  except:
    pass
else:
  print(ans)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
 
train = [[0 for i in range(N+1)] for j in range(N+1)]
for m in range(M):
    L,R = map(int,input().split())
    train[L][R] += 1
 
c = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    cnt = 0
    for j in range(1,N+1):
        cnt += train[i][j]
        c[i][j] = cnt


for x in range(Q):
    p,q = map(int,input().split())
    cnt2 = 0
    for i in range(p,q+1):
        cnt2 += c[i][q] - c[i][p-1]
    print(cnt2)

### FIXED CODE ###

N,M,Q = map(int,input().split())

train = [[0 for i in range(N)] for j in range(N)]
for m in range(M):
    L,R = map(int,input().split())
    train[L-1][R-1] += 1

c = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    cnt = 0
    for j in range(N):
        cnt += train[i][j]
        c[i][j] = cnt

for x in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    cnt2 = 0
    for i in range(p,q+1):
        if p == 0:
            cnt2 += c[i][q]
        else:
            cnt2 += c[i][q] - c[i][p-1]
    print(cnt2)
### BUGGY CODE ###

def main():
    N,Q = list(map(int,input().split()))
    edges = [[] for i in range(N+1)]
    for i in range(N-1):
        a,b = list(map(int,input().split()))
        edges[a].append(b)
        edges[b].append(a)

    add = [0]*(N+1)
    for i in range(Q):
        p,x = list(map(int,input().split()))
        add[p] += x

    stack = [(1,0)]
    ans = [0]*(N+1)
    not_checked = [True]*(N+1)
    while stack:
        v,cnt = stack.pop()
        ans[v] = cnt+add[v]
        not_checked[v] = False
        for edge in edges[v]:
            if not_checked[edge]:
                stack.append((edge,ans[v]))

    for i in range(1,N):
        print(ans[i],end=" ")
    print(ans[N])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    N,Q = list(map(int,input().split()))
    edges = [[] for i in range(N+1)]
    for i in range(N-1):
        a,b = list(map(int,input().split()))
        edges[a].append(b)
        edges[b].append(a)

    add = [0]*(N+1)
    for i in range(Q):
        p,x = list(map(int,input().split()))
        add[p] += x

    stack = [(1,0)]
    ans = [0]*(N+1)
    not_checked = [True]*(N+1)
    while stack:
        v,cnt = stack.pop()
        ans[v] = cnt+add[v]
        not_checked[v] = False
        for edge in edges[v]:
            if not_checked[edge]:
                stack.append((edge,ans[v]))

    for i in range(1,N):
        print(ans[i],end=" ")
    print(ans[N])

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

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
R,G,B,N = map(int,input().split())

ans = 0
for r in range(N//R + 1):
    for g in range(N//G +1):
        rest = N - R*r - G*g
        if rest >= 0 and rest%B == 0:
            # print(r,g,rest//B)
            ans +=1

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
R,G,B,N = map(int,input().split())

ans = 0
for r in range(N//R + 1):
    for g in range(N//G +1):
        rest = N - R*r - G*g
        if rest >= 0 and rest%B == 0:
            # print(r,g,rest//B)
            ans +=1

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        A[new_x][new_y] = depth+1

print(depth)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1

print(depth)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

import heapq
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10**30
for x in b:
	removed = []
	que = []
	for i in range(n+2):
		if a[i] < x:
			if len(que) >= k:
				removed += heapq.nsmallest(len(que)-k+1, que)
			que = []
		else:
			que.append(a[i])
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)

### FIXED CODE ###

import sys, heapq
def input():
	return sys.stdin.readline()[:-1]

n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10**30
for x in b:
	removed = []
	que = []
	for i in range(n+2):
		if a[i] < x:
			que = []
		else:
			heapq.heappush(que, a[i])
			if len(que) == k:
				removed.append(heapq.heappop(que))
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n = int(input())
a = np.array(input().split(), dtype='int')

ans = ''
count_all = 0

for j in range(n):
    num = a[0]
    if len(a[a == num]) != 1:
        ans = 'NO'
        break
    a = np.delete(a, 0)
    
if ans == 'NO':
    print(ans)
else:
    print('YES')

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n = int(input())
a = np.array(input().split(), dtype='int')

a_sort = np.sort(a)
ans = ''

for i in range(n - 1):
    if a_sort[i] == a_sort[i + 1]:
        ans = 'NO'
        break
    
if ans == 'NO':
    print(ans)
else:
    print('YES')
### BUGGY CODE ###

def comb(n, r):
    bunshi = 1
    for i in range(n-r+1,n+1):
        bunshi = bunshi*i
    bunbo = 1
    for i in range(1,r+1):
        bunbo = bunbo * i 
    return bunshi//bunbo

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

def count(index, l):
    counted = []
    duplication = []
    for x in l:
        if x in counted:
            continue
        if l.count(x) > 0:
            duplication.append(l.count(x))
            counted.append(x)
    ans = 0
    for x in duplication:
        ans += comb(x,2)
    print(ans)

for i in range(N):
    l = A[:]
    del l[i]
    count(i, l)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# TLE
def test():
    duplication = {}
    ans = 0
    for x in A:
        if x in duplication:
            continue
        count = A.count(x)
        if count > 1:
            duplication[x] = count
            ans += count*(count-1)//2
    for x in A:
        if x not in duplication:
            print(ans)
        else:
            print(ans -(duplication[x]-1))
from collections import defaultdict

sum = 0
count_dic = defaultdict(int)
for x in A:
    count_dic[x] +=1
for v in count_dic.values():
    sum += v*(v-1)//2
for x in A:
    print(sum -(count_dic[x]-1))
### BUGGY CODE ###

# AtCoder Beginner Contest 100
# C - *3 or /2

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

count=0

A=[ a for a in A if a%2==0 ]

while len(A)>0:
    _A=[]
    for a in A:
        if a==max(A):
            _a=a//2
            if _a%2==0:
                _A.append(_a)
            else:
                pass
        else:
            if a%2==0:
                _a=a*3
                _A.append(_a)
            else :
                pass
    count+=1
    A=_A
    # print(A)
    # print(_A)

print(count)


### FIXED CODE ###

# AtCoder Beginner Contest 100
# C - *3 or /2
def f(N,c):
    if N%2==0:
        n=N//2
        c+=1
        return f(n,c)
    else:
        return c



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

count=0

for a in A:
    count+= f(a,0)

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

import math
N = int(input())
for i in range(1, N+1):
    cnt = 0
    for x in range(1, 45):
        for y in range(1, 45):
            for z in range(1, 45):
                if ((x+y+z)**2)-x*y-y*z-z*x == i:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

N = int(input())
lis = [0]*N
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x -1
            if ans >= N:
                pass
            else:
                lis[ans] += 1
for i in range(N):
    print(lis[i])
### BUGGY CODE ###

N = int(input())
S = list(str(input()))
from collections import Counter

c = Counter(S)
ans = c['B']*c['G']*c['R']
for i in range(N-1):
    for j in range(i, N):
        if S[i]==S[j]:
            continue
        c_lis = ['R', 'G', 'B']
        c_lis.remove(S[i])
        c_lis.remove(S[j])
        chara = c_lis[0]
        try:
            if S[i+(j-i)*2]==chara:
                ans-=1
        except:
            pass
print(ans)

### FIXED CODE ###

N = int(input())
S = list(str(input()))
from collections import Counter

c = Counter(S)
ans = c['B']*c['G']*c['R']
for i in range(N-1):
    for j in range(i, N):
        if S[i]==S[j]:
            continue
        elif i+(j-i)*2>N-1:
            break
        s = S[i+(j-i)*2]
        if s!=S[i] and s!=S[j]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=10**9
dp=[INF for i in range(n)]
dp[0]=0
if k>n-1:
    k=n-1
for i in range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=10**9
dp=[INF for i in range(n)]
dp[0]=0
if k>n-1:
    k=n-1
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            break
        dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

from numpy import*
a,b=loadtxt(open(0),'i',skiprows=1)
c=0
l=2**29
while l:u=l;l//=2;c+=sum(diff(searchsorted(sort(hstack((b%u-u,b%u))),[u-a%u,l-a%u]).T))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:h=l;l//=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
  ans += a[i]*sum(a[i+1:])
  ans %= 10**9+7
print(ans)

### FIXED CODE ###

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

mod = 10**9+7
nums = [0]*n
nums[0] = a[0]
for i in range(1,n): nums[i] = a[i] + nums[i-1]

ans = 0
for i in range(n-1):
  ans += a[i] * (nums[n-1]-nums[i])
  ans %= mod
print(ans)
### BUGGY CODE ###

R, C, K = map(int, input().split())
dp = [[[0 for i in range(4)] for j in range(C+1)] for k in range(R+1)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]

for i in range(K):
    r, c, v = map(int, input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[i-1][j])
            dp[i][j][0] = max(dp[i][j-1][0], M)
            dp[i][j][1] = max(dp[i][j-1][0]+v, dp[i][j-1][1], M+v)
            dp[i][j][2] = max(dp[i][j-1][1]+v, dp[i][j-1][2])
            dp[i][j][3] = max(dp[i][j-1][2]+v, dp[i][j-1][3])

        else:
            M = max(dp[i-1][j])
            dp[i][j][0] = max(dp[i][j-1][0], M)
            dp[i][j][1] = dp[i][j-1][1]
            dp[i][j][2] = dp[i][j-1][2]
            dp[i][j][3] = dp[i][j-1][3]

ans = 0
for i in range(4):
    ans = max(ans, dp[-1][-1][i])
print(ans)


### FIXED CODE ###

R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)
### BUGGY CODE ###

def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
def divisor_num(n):
    a = 1
    for _, x in factorization(n):
        a *= x + 1
    return a
N=int(input())
ans=0
li=[i for i in range(1,N+1)]
for i in range(1,N+1):
  ans+=divisor_num(i)*i
print(ans)


### FIXED CODE ###

N=int(input())
ans=(N*(N+1))//2  #1の時
for i in range(2,N+1):
  m=N//i
  ans+=i*(m*(m+1)//2)
print(ans)