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

def resolve():
    n, m = map(int, input().split())

    ac_list = []
    penalties = 0
    wa_counts = [0] * n

    for _ in range(m):
        line = input().split()
        q = int(line[0])
        r = line[1]

        if q not in ac_list:
            if r == 'WA':
                wa_counts[q-1] += 1

            else:
                ac_list.append(q)
                penalties += wa_counts[q-1]

    print(len(ac_list), penalties)

resolve()


### FIXED CODE ###

def resolve():
    n, m = map(int, input().split())

    penalties = 0
    wa_counts = [0] * n
    ac_flags = [0] * n

    for _ in range(m):
        line = input().split()
        q = int(line[0])
        r = line[1]

        if ac_flags[q-1] == 0:
            if r == 'WA':
                wa_counts[q-1] += 1

            else:
                ac_flags[q-1] = 1
                penalties += wa_counts[q-1]

    print(sum(ac_flags), penalties)
    
resolve()
### BUGGY CODE ###

from operator import itemgetter

D, G = map(int, input().split())
PC = [list(map(int, input().split())) for _ in range(D)]

def score(d, n, s, ans):
    if s >= G:
        ans = min(ans, n)
        return ans
    if d == D:
        if s >= G:
            ans = min(ans, n)
        return ans
    p, c = PC[d]
    for k in range(p+1):
        if k == p:
            ans = score(d+1, n+k, 100*(d+1)*k + c + s, ans)
        else:
            ans = score(d+1, n+k, 100*(d+1)*k + s, ans)
    return ans

print(score(0, 0, 0, 1000))

### FIXED CODE ###

from operator import itemgetter

D, G = map(int, input().split())
PC = [list(map(int, input().split())) for _ in range(D)]

def com(d, s, ans):
    if d == D:
        ans.append(s)
        return ans
    a = s[:]
    a.append(1)
    ans = com(d+1, a, ans)
    b = s[:]
    b.append(0)
    ans = com(d+1, b, ans)
    return ans

L = com(0, [], [])
ans = 10000
for l in L:
    point = 0
    probs = 0
    uncom = []
    for i, com in enumerate(l):
        if com == 0:
            uncom.append(i)
        else:
            p, c = PC[i]
            point += (i+1)*100*p + c
            probs += p
    #print(probs, l)
    if point >= G:
        ans = min(ans, probs)
        continue
    uncom.sort(reverse=True)
    re = G - point
    for un in uncom:
        p, c = PC[un]
        #print(re, probs, p)
        if (un+1)*100*(p-1) >= re:
            rem = 1 if re % ((un+1)*100) > 0 else 0
            probs += re // ((un+1)*100) + rem
            re = 0
            break
        re -= (un+1)*100*(p-1)
        probs += p-1
    #print(probs)
    if re > 0:
        continue
    ans = min(ans, probs)
print(ans)
### BUGGY CODE ###

from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n = int(input())
da = NextIntList()
da = sorted(da)
ans = 1
for i in range(n):
    ans *= da[i]
    if ans > 10**18:
        ans = -1

if ans < 0:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n = int(input())
da = NextIntList()
da = sorted(da)
ans = 1
for i in range(n):
    ans *= da[i]
    if ans > 10**18:
        ans = -1
    elif ans < 0:
        ans = -1

if ans < 0:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from copy import deepcopy
from collections import deque
def main():
    h, n = map(int, input().split())
    a = deque()
    b = deque()
    aa = a.append
    ba = b.append
    for _ in range(n):
        numa, numb = map(int, input().split())
        aa(numa)
        ba(numb)
    dp = [10**9] * (h + 1)
    dp[0] = 0
    while a:
        dp_c = deepcopy(dp)
        at = a.popleft()
        bt = b.popleft()
        for i1 in range(h + 1):
            if i1 <= at:
                dp[i1] = min(bt, dp_c[i1])
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - at] + bt)
    print(dp[h])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

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

n,k,*h=map(int,open(0).read().split())
a=[0]*n
for i in range(1,n):
    j=max(0,i-k)
    a[i]=min(A+abs(h[i]-H) for A,H in zip(a[j:i],h[j:i]))
print(a[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
dp=[10**9]*n
dp[0]=0
dp[1]=abs(a[1]-a[0])
for i in range(2,n):
    for j in range(max(0,i-k),i):
        dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

alf=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
N=int(input())
li=[]
for h in range(N):
    li.append([0]*26)
for i in range(N):
    s=input()
    for j in range(10):
        num=alf.index(s[j])
        li[i][num]+=1
ans=0       
for k in range(N):
    for l in range(N):
        if k<l:
            if li[k]==li[l]:
                ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
ans=0
li=[]
for i in range(N):
    s=list(input())
    s.sort()
    li.append(s)
li.sort()
temp=1
for j in range(N-1):
    if li[j]==li[j+1]:
        temp+=1
    else:
        ans+=temp*(temp-1)//2
        temp=1
        
ans+=temp*(temp-1)//2
print(ans)
### BUGGY CODE ###

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

INF=1000000000000000000

ans=1
for n in range(N):
    ans*=A[n]

if ans>INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

INF=1000000000000000000
if 0 in A:
    print(0)
else:
    ans=1
    for n in range(N):
        ans*=A[n]
        if ans>INF:
            break

    if ans>INF:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

import heapq

INF = 10**18

n,m,s,t = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(m)]

graph_s = [[] for _ in range(n)]
graph_t = [[] for _ in range(n)]

for e in edge:
    graph_s[e[0]-1].append([e[1]-1,e[2]])
    graph_s[e[1]-1].append([e[0]-1,e[2]])
    graph_t[e[0]-1].append([e[1]-1,e[3]])
    graph_t[e[1]-1].append([e[0]-1,e[3]])

dist_s = [INF]*n
dist_t = [INF]*n

dist_s[s-1] = 0
dist_t[t-1] = 0

heap_s = [[0,s-1]]
heapq.heapify(heap_s)

heap_t = [[0,t-1]]
heapq.heapify(heap_t)

while heap_s:
    cost,node = heapq.heappop(heap_s)
    if dist_s[node] < cost:
        continue
    for adj,adjcost in graph_s[node]:
        if dist_s[node] + adjcost < dist_s[adj]:
            dist_s[adj] = dist_s[node] + adjcost
            heapq.heappush(heap_s,[dist_s[adj],adj])

while heap_t:
    cost,node = heapq.heappop(heap_t)
    if dist_t[node] < cost:
        continue
    for adj,adjcost in graph_t[node]:
        if dist_t[node] + adjcost < dist_t[adj]:
            dist_t[adj] = dist_t[node] + adjcost
            heapq.heappush(heap_t,[dist_t[adj],adj])

dist = INF
ans = []
                                              
for i in range(n):
    dist = min(dist,dist_t[-1-i]+dist_s[-1-i])
    ans.append(10**15-dist)
    
for i in range(n):
    print(ans[-1-i])

### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline
INF = 10**18

n,m,s,t = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(m)]

graph_s = [[] for _ in range(n)]
graph_t = [[] for _ in range(n)]

for e in edge:
    graph_s[e[0]-1].append([e[1]-1,e[2]])
    graph_s[e[1]-1].append([e[0]-1,e[2]])
    graph_t[e[0]-1].append([e[1]-1,e[3]])
    graph_t[e[1]-1].append([e[0]-1,e[3]])

dist_s = [INF]*n
dist_t = [INF]*n

dist_s[s-1] = 0
dist_t[t-1] = 0

heap_s = [[0,s-1]]
heapq.heapify(heap_s)

heap_t = [[0,t-1]]
heapq.heapify(heap_t)

while heap_s:
    cost,node = heapq.heappop(heap_s)
    if dist_s[node] < cost:
        continue
    for adj,adjcost in graph_s[node]:
        if dist_s[node] + adjcost < dist_s[adj]:
            dist_s[adj] = dist_s[node] + adjcost
            heapq.heappush(heap_s,[dist_s[adj],adj])

while heap_t:
    cost,node = heapq.heappop(heap_t)
    if dist_t[node] < cost:
        continue
    for adj,adjcost in graph_t[node]:
        if dist_t[node] + adjcost < dist_t[adj]:
            dist_t[adj] = dist_t[node] + adjcost
            heapq.heappush(heap_t,[dist_t[adj],adj])

dist = INF
ans = []
                                              
for i in range(n):
    dist = min(dist,dist_t[-1-i]+dist_s[-1-i])
    ans.append(10**15-dist)
    
for i in range(n):
    print(ans[-1-i])
### BUGGY CODE ###

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

flag = True

for i in query:
    if i[0]=="1":
        flag = not flag
#        S=S[::-1]
    else:
        if flag:
            if i[1]=="1":
                S=i[2]+S
            else:
                S=S+i[2]
        else:
            if i[1]=="1":
                S=S+i[2][::-1]
            else:
                S=i[2][::-1]+S
if flag:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

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

flag = True
t=""
u=""

for i in query:
    if i[0]=="1":
        u,t=t,u
        flag = not flag
#        S=S[::-1]
    else:
        if i[1]=="1":
            t+=i[2]
        else:
            u+=i[2]
if flag:
    print(t[::-1]+S+u)
else:
    print(t[::-1]+S[::-1]+u)
### BUGGY CODE ###

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

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        dp[y][x]=grid(y-1,x)+grid(y,x-1)
    return dp[y][x]

H,W=map(int,input().split())
mp=[['#']*(W+1)]
for _ in range(H):
    mp.append(['#']+list(input()))
mp.append(['#']*(W+1))

dp=[[0]*(W+1) for _ in range(H+1)]
dp[1][1]=1
grid(H,W)
print(dp[H][W]%(10**9+7))


### FIXED CODE ###

import sys
input=sys.stdin.readline

def grid(y,x,mp):
    mod=10**9+7
    dp=[[0]*x for _ in range(y)]
    dp[0][0]=1
    for h in range(y):
        for w in range(x):
            if mp[h][w]=='.':
                if 1<=h<y and 1<=w<x:
                    dp[h][w]=((dp[h][w-1]+dp[h-1][w])%mod)
                elif h==0 and 1<=w<x:
                    dp[h][w]=(dp[h][w-1]%mod)
                elif 1<=h<y and w==0:
                    dp[h][w]=(dp[h-1][w]%mod)
    return dp[y-1][x-1]


H,W=map(int,input().split())
mp=[list(input()) for _ in range(H)]
print(grid(H,W,mp))
### BUGGY CODE ###

n = int(input())
array = [int(x) for x in input().split(' ')]
s = 0
for i in range(n):
    for j in range(i+1, n):
        s += (array[i] * array[j])

print(s % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
array = [int(x) for x in input().split(' ')]
s = 0
sums = []
for i in range(n-1, -1, -1):
    if i == n-1:
        sums.append(array[i])
    else:
        sums.append(sums[-1] + array[i])

sums.pop()
for i in range(n-1):
    s += array[i] * sums.pop()

print(s % (10 ** 9 + 7))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10**9+7
for i in range(N):
    for j in range(i+1, N):
        ans += A[i]*A[j] % MOD
        ans %= MOD
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
s = sum(A)
ans = 0
MOD = 10**9+7
for i in range(N):
    s -= A[i]
    ans += s*A[i] % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%15==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)

### FIXED CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)
### BUGGY CODE ###

#!/usr/bin/env python3


import numpy as np


def solv(m, a):
    boxs = np.zeros(m, dtype=np.uint16)

    for i in range(m, 0, -1):
        idx = np.arange(i+i-1, m, i)
        s = np.sum(boxs[idx])
        boxs[i-1] = (s + a[i-1]) % 2

    return boxs


if __name__ == '__main__':

    m = int(input())
    a = np.array(list(map(int, input().split())), dtype=np.uint16)

    ans = solv(m, a)

    print(sum(ans))
    for i in range(m):
        if ans[i]:
            print(i+1)


### FIXED CODE ###

#!/usr/bin/env python3


import numpy as np


def solv(m, a):
    boxs = np.zeros(m, dtype=np.int)

    for i in range(m, 0, -1):
        # idx = np.arange(i+i-1, m, i)
        s = np.count_nonzero(boxs[i+i-1:m:i])
        boxs[i-1] = (s + a[i-1]) % 2

    return boxs


if __name__ == '__main__':

    m = int(input())
    a = np.array(list(map(int, input().split())), dtype=np.int)

    ans = solv(m, a)

    print(sum(ans))
    for i in range(m):
        if ans[i]:
            print(i+1)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = []
L = []
for i in range(N):
    A.append(K)
for i in range(Q):
    L.append(int(input()))
for i in range(Q):
    for j in range(N):
        if j == L[i] - 1:
            pass
        else:
            A[j] -= 1

for i in range(N):
    if A[i] <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = []
L = []
for i in range(N):
    A.append(K - Q)
for i in range(Q):
    L.append(int(input()))
for i in range(Q):
    j = L[i]
    A[j - 1] += 1

for i in range(N):
    if A[i] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math
N , M = map(int, input().split())
A = list(map(int , input().split()))
#print(A)
for _ in range(M):
    max_index = A.index(max(A))
    A[max_index] = A[max_index] / 2
A = list(map( lambda x : math.floor(x) , A ))
print(sum(A))


### FIXED CODE ###

import math
import heapq
N , M = map(int, input().split())
A = list(map(int , input().split()))
A = list(map( lambda x : x * (-1) , A ))
heapq.heapify(A)
for _ in range(M):
    tmp = heapq.heappop(A) * (-1) / 2
    heapq.heappush(A,tmp * (-1))
A = list(map( lambda x : x * (-1) , A ))
A = list(map( lambda x : math.floor(x) , A ))
print(sum(A))
### BUGGY CODE ###

import math
from functools import reduce
import itertools

K = int(input())
count = 0
for abc in list(itertools.product(list(range(1, K+1)), repeat=3)):
    count += reduce(math.gcd, abc)

print(count)

### FIXED CODE ###

import math

count = 0

K = int(input())
for a in range(1, K+1):
    for b in range(1, K+1):
        temp = math.gcd(a, b)
        for c in range(1, K+1):
            count += math.gcd(temp, c)

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

from collections import deque
def inputs(): return [int(x) for x in input().split()]
s = deque(input())
q = int(input())
for i in range(q):
    q1 = input()
    if len(q1)==1:
        s = list(s)
        s = deque(s[::-1])
    else:
        l,f,c = q1.split()
        if int(f)==1:
            s.appendleft(c)
        else:
            s.append(c)
print("".join(list(s)))


### FIXED CODE ###

from collections import deque
def inputs(): return [int(x) for x in input().split()]
s = deque(input())
q = int(input())
flag = 1
for i in range(q):
    q1 = input()
    if len(q1)==1:
      flag *=-1 
    else:
        l,f,c = q1.split()
        if flag ==1:
            if int(f)==1:
                s.appendleft(c)
            else:
                s.append(c)
        elif flag==-1:
            if int(f)==1:
                s.append(c)
            else:
                s.appendleft(c)
if flag==1:
    print("".join(list(s)))
else:
    s = list(s)
    s = s[::-1]
    print("".join(list(s)))
### BUGGY CODE ###

N = int(input())
edges = [[int(i) for i in input().split()] for _ in range(N-1)]
edge_col = [0]*(N-1)
cols = [set() for _ in range(N)]
gp = [[] for _ in range(N)]

for ind, (a, b) in enumerate(edges):
    gp[a-1].append((b-1, ind))
    gp[b-1].append((a-1, ind))

def dfs():
    seen = set()
    stk = [0]
    while stk:
        pt = stk.pop()
        if(pt in seen):
            continue
        seen.add(pt)
        for nxt, ind in gp[pt]:
            if(nxt in seen):
                continue
            col = 1
            while col in cols[pt]:
                col += 1
            edge_col[ind] = col
            cols[pt].add(col)
            cols[nxt].add(col)

            stk.append(nxt)

dfs()
print(max(edge_col))
for i in edge_col:
    print(i)


### FIXED CODE ###

N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
#K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)
### BUGGY CODE ###

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

while len(list) <= N:
  i = 0
  for i in range(A):
    list.append('b')
  
  if len(list) <= N:
    i = 0
    for i in range(B):
      list.append('r')
    
for i in range(N):
  if list[i] == 'b':
    count += 1
    
print(count)
  

### FIXED CODE ###

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

a = N // (A+B)

if N % (A+B) >= A:
  print(a*A+A)
  
else:
  print(a*A + N % (A+B))
### BUGGY CODE ###

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

import math


def g(nx, ny, nz):
    return nx ** 2 + ny ** 2 + nz ** 2 + nx * ny + ny * nz + nz * nx


def is_int(fn):
    return float(int(fn)) == float(fn)


def solve(n):
    min_z = max(1, int(math.sqrt(n) / 3))
    max_z = max(1, int(math.sqrt(n - 2) - 1) if n > 2 else 1)
    max_x = max(1, int(math.sqrt(n / 3) + 1))
    
    counter = 0
    
    for z in range(max(1, min_z), max_z + 1):
        for y in range(1, z + 1):
            for x in range(1, min(y + 1, max_x)):
                if g(x, y, z) == n:
                    counter += 1
    
    counter *= 3
    
    if is_int(math.sqrt(n / 6)):
        counter -= 2
    
    print(counter, flush=True)


N = int(input())

for ni in range(1, N + 1):
    solve(ni)


### FIXED CODE ###

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

import math


def g(nx, ny, nz):
    return nx ** 2 + ny ** 2 + nz ** 2 + nx * ny + ny * nz + nz * nx


def solve(n):
    # min_z = max(1, int(math.sqrt(n) / 3))
    max_z = max(1, int(math.sqrt(n - 2) - 1) if n > 2 else 1)
    # max_x = max(1, int(math.sqrt(n / 3) + 1))
    
    counter = [0 for _ in range(n + 1)]
    
    for z in range(1, max_z + 1):
        for y in range(1, max_z + 1):
            for x in range(1, max_z + 1):
                gn = g(x, y, z)
                if gn <= n:
                    counter[gn] += 1
    
    for i in range(1, n + 1):
        print(counter[i])


N = int(input())

solve(N)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
ac = [0] * N

for i in range(N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        ac[i + 1] = 1

for i in range(Q):
    l, r = map(int, input().split())
    print(sum(ac[l:r]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
ac = [0] * N
j = 0
for i in range(N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        j += 1
    ac[i + 1] += j

for i in range(Q):
    l, r = map(int, input().split())
    print(ac[r - 1] - ac[l - 1])
### BUGGY CODE ###

s = input()
n = len(s)


def divide(x):
    a = "".join(x.split("01"))
    b = "".join(a.split("10"))
    return b


def judge(x):
    return len(x.split("01")) == 1 and len(x.split("10")) == 1


while not judge(s):
    s = divide(s)

print(n - len(s))


### FIXED CODE ###

s = input()
n = len(s)
num_0 = s.count("0")
num_1 = n - num_0

print(n - abs(num_0 - num_1))
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(n):
    ans += i
print(ans)



### FIXED CODE ###

n = int(input())

print(n * (n - 1) // 2)
### BUGGY CODE ###

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
for _ in range(m):
    b, c = map(int, input().split())
    a_list.extend([c]*b)
a_list.sort(reverse=True)
print(sum(a_list[:n]))


### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list.append([c, b])
m_list.sort(reverse=True)
cnt = 0
tmp_list = []
for c, b in m_list:
    if cnt < n:
        tmp_list += [c]*b
    else:
        break
    cnt += b
a_list.extend(tmp_list)
a_list.sort(reverse=True)
print(sum(a_list[:n]))
### BUGGY CODE ###

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

ans = 0
for i in range(60):
    cont = 0
    for j in range(n):
        if (a[j] >> i & 1):
            cont += 1
    now = cont * (n-cont) % mod
    for j in range(i):
        now  = now * 2 % mod
    ans += now
    ans %= mod
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(60):
    cont = 0
    for j in range(n):
        if (a[j] >> i & 1):
            cont += 1
    now = cont * (n-cont) % mod
    for j in range(i):
        now  = now * 2 % mod
    ans += now
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        ain = [int(j) for j in input().split()]
        for j in range(N): A[i][j] = ain[j]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()