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

import sys
input=sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k=map(int, input().split())

tk=UnionFind(n)

kk=[[False] * n for _ in range(n)]

for _ in range(m):
    a,b=map(int, input().split())
    kk[a-1][b-1]=True
    kk[b-1][a-1]=True
    tk.union(a-1, b-1)

for _ in range(k):
    c,d=map(int, input().split())
    kk[c-1][d-1]=True
    kk[d-1][c-1]=True

for i in range(n):
    ans=-1
    for j in range(n):
        if not kk[i][j] and tk.same(i, j):
            ans+=1
    print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

n,m,k=map(int, input().split())

tk=UnionFind(n)

stk=[0 for _ in range(n)]
blk=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int, input().split())
    stk[a-1]+=1
    stk[b-1]+=1
    tk.union(a-1, b-1)

for _ in range(k):
    c,d=map(int, input().split())
    blk[c-1].append(d-1)
    blk[d-1].append(c-1)

for i in range(n):
    ans=tk.get_size(i)-1-stk[i]
    for j in blk[i]:
        if tk.is_same(i, j):
            ans-=1
    print(ans)
### BUGGY CODE ###

N = int(input())
P = input().split()
count = 0

for i in range(N):
  flag = True
  for j in range(i):
    if int(P[i]) > int(P[j]):
      flag = False
      break
  if flag:
    count += 1
print(count)


### FIXED CODE ###

N = int(input())
P = input().split()
count = 0
cur_min = int(P[0])

for i in range(N):
  if cur_min >= int(P[i]):
    cur_min = int(P[i])
    count += 1
print(count)
### BUGGY CODE ###

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

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

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

A.sort()
if A[0] == 0:
    print(0)
else:
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10 ** 18:
            ans = -1
            break

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

import copy
 
N,Q = map(int,input().split())
A = list(map(int,input().split()))
X = [0]*Q
 
for i in range(Q):
  X[i] = int(input())
  #初期値
  j= -1
  Takahashi = 0
  Aoki = 0
  B = copy.deepcopy(A)
  flag =0
  
  for k in range(N):
    if flag == 0: #高橋くんの行動
      Takahashi += B[-1]
      del B[-1]
      flag = 1
    
    elif flag ==1: #青木くんの行動
      
      #j-1番目のカード値B[j-1] <= 青木くんが決めた整数X[i] < j番目のカード値B[j]
      #となるようにjの値を決める
      #ただしX[i]がいずれのBの要素よりも大きい場合はi=N-k-1とする
      if j == -1:
        for l in range(N-k):
          if X[i] < B[l]:
            j = l 
            break
        if j == -1:
          j = N-k-1
          
      if len(B) == j:
         j = len(B)-1

          
      #j=0（青木くんが決めた整数は残りカードのいずれよりも小さい）の場合、B[0]を取る
      if j == 0:
        Aoki +=B[0]
        del B[0]
        flag =0
      #j=0（青木くんが決めた整数は残りカードのいずれよりも小さい）の場合、B[0]を取る
      #j番目のカードB[j]を取る     
      elif abs(X[i]-B[j]) < abs(X[i]-B[j-1]):
        Aoki += B[j]
        del B[j]
        flag =0
        if len(B) == j:
           j=j-1
      #j番目のカードB[j-1]を取る   
      else:
        Aoki += B[j-1]
        del B[j-1]
        flag = 0
        j = j-1
  print(Takahashi)

### FIXED CODE ###

n,q = map(int,input().split())
a = list(map(int,input().split()))
query = [int(input()) for i in range(q)]

a = sorted(a)
ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]
    
ruiseki2 = [0]*(n+1)
if n % 2 == 1:
    for i in range(n):
        if i % 2 == 0:
            ruiseki2[i+1] = ruiseki2[i] + a[i]
        else:
            ruiseki2[i+1] = ruiseki2[i]

if n % 2 == 0:
    for i in range(n):
        if i % 2 == 1:
            ruiseki2[i+1] = ruiseki2[i] + a[i]
        else:
            ruiseki2[i+1] = ruiseki2[i]

def solve(mid, num):
    r = -((-mid) // 2)
    l = mid
    r_pos = n - r
    l_pos = n - l
    if abs(a[l_pos] - num) <= abs(a[r_pos] - num):
        return True
    else:
        return False

for i in range(q):
    num = query[i]
    ok = 1
    ng = n + 1 
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid, num):
            ok = mid
        else:
            ng = mid
    ans = 0
    ans += ruiseki[n] - ruiseki[n-(ok+1)//2]
    nokori = n - ok
    ans += ruiseki2[nokori]
    print(ans)
### BUGGY CODE ###

#encoding utf-8

import copy
import numpy as np
import random


s = list(str(input()))
k = int(input())

substrings = []
for length in range(1,len(s)+1):
    for i in range(len(s)-length+1):
        word = "".join(s[i:i+length])
        # print(word)

        if word in substrings:
            pass
        else:
            substrings.append(str(word))

substrings.sort()
# print(substrings)
print(substrings[k-1])


### FIXED CODE ###

#encoding utf-8

import copy
import numpy as np
import random


s = list(str(input()))
k = int(input())

substrings = []
for length in range(1,len(s)+1):
    if length > 5:
        break
    for i in range(len(s)-length+1):
        word = "".join(s[i:i+length])
        # print(word)
        if word in substrings:
            pass
        else:
            substrings.append(str(word))

substrings.sort()
# print(substrings)
print(substrings[k-1])
### BUGGY CODE ###

n, m, p = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for _ in range(m)]

for i in e:
    i[0] -= 1
    i[1] -= 1
    i[2] -= p

d = [-10**18] * n
ok1 = [False] * n
ok2 = [False] * n
d[0] = 0
ok1[0] = True
ok2[-1] = True

for _ in range(n):
    for a, b, c in e:
        if ok1[a]:
            d[b] = max(d[b], d[a] + c)
            ok1[b] = True
        if ok2[b]:
            ok2[a] = True
aa = d[:]

for _ in range(1):
    for a, b, c in e:
        if ok1[a]:
            d[b] = max(d[b], d[a] + c)
            ok1[b] = True
        if ok2[b]:
            ok2[a] = True

bb = d[:]

ok = False
for i in range(n):
    if ok1[i] and ok2[i]:
        if aa[i] != bb[i]:
            ok = True
if ok:
    print("-1")
else:
    print(max(aa[-1], 0))


### FIXED CODE ###

n, m, p = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for _ in range(m)]

for i in e:
    i[0] -= 1
    i[1] -= 1
    i[2] -= p

d = [-10**18] * n
ok1 = [False] * n
ok2 = [False] * n
d[0] = 0
ok1[0] = True
ok2[-1] = True

for _ in range(n):
    for a, b, c in e:
        if ok1[a]:
            d[b] = max(d[b], d[a] + c)
            ok1[b] = True
        if ok2[b]:
            ok2[a] = True
aa = d[:]

for _ in range(n):
    for a, b, c in e:
        if ok1[a]:
            d[b] = max(d[b], d[a] + c)
            ok1[b] = True
        if ok2[b]:
            ok2[a] = True

bb = d[:]

ok = False
for i in range(n):
    if ok1[i] and ok2[i]:
        if aa[i] != bb[i]:
            ok = True
if ok:
    print("-1")
else:
    print(max(aa[-1], 0))
### BUGGY CODE ###

h, n = [int(i) for i in input().split()]
a, b = [0]*n, [0]*n

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]
    if eff < a[i]/b[i]:
        eff = a[i]/b[i]
        eff_index = i

max_kaisuu = - (-h//a[eff_index])

ans = float('inf')
H = max_kaisuu * b[eff_index]
dp = [[0] * (H+1) for _ in range(n+1)]
# dp[i][j] i番目までの魔法で消費魔力がjを超えないように選んだときのダメージの最大値
for i in range(n):
    for j in range(H+1):
        if j < b[i]:# i番目の魔法消費b[i]がjを超えているので，入れる可能性がない

            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-b[i]]+a[i])# 入れ場合と入れない場合を比較

        if dp[i+1][j] >= h:
            ans = min(ans, j)
            continue
print(ans)


### FIXED CODE ###

h, n = [int(i) for i in input().split()]
a, b = [0]*n, [0]*n

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]

max_a = max(a)

ans = float('inf')
H = h + max_a
dp = [float('inf')] * (H+1)
# dp[i] iのダメージを与える最小消費魔力
dp[0] = 0
for i in range(H+1):
    for j in range(n):
        if i >= a[j]:
            dp[i] = min(dp[i], dp[i-a[j]]+b[j])

    if i >= h:
        ans = min(ans, dp[i])
print(ans)
### BUGGY CODE ###


from collections import defaultdict

def get_p(ind, parent):
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind, parent):
    while parent[ind] != -1:
        ind = parent[ind]
    return ind


def main():
    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [-1 for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        if parent[a] == -1 and parent[b] == -1:
            parent[max(a, b)] = min(a, b)
        elif parent[a] != -1 and parent[b] != -1:
            a_parent = get_p2(a, parent)
            b_parent = get_p2(b, parent)
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)
        elif parent[a] == -1:
            parent[a] = parent[b]
        else:
            parent[b] = parent[a]


    ans = 0

    for i in range(num + 1):
        if parent[i] == -1:
            parent[i] = i


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int, parent) == get_p(ind, parent):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###



def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind =  data[i]
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

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

import sys, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(d)
    d = d
    for i in range(V):
        d[i][i] = 0
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def resolve():
    N = I()
    A = [LI() for _ in range(N)]

    min_cost = copy.deepcopy(A)
    min_cost = warshall_floyd(min_cost)
    ans = copy.deepcopy(min_cost)

    if A == min_cost:
        for i in range(N):
            for j in range(N):
                if i!=j:
                    for k in range(N):
                        if k!=i and k!=j:
                            if min_cost[i][j]==min_cost[i][k]+min_cost[k][j]:
                                ans[i][j] = 0
        print(sum([sum(i) for i in ans])//2)
    else:
        print(-1)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

import sys, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(d)
    d = d
    for i in range(V):
        d[i][i] = 0
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def resolve():
    N = I()
    A = [LI() for _ in range(N)]

    min_cost = copy.deepcopy(A)
    min_cost = warshall_floyd(min_cost)
    ans = copy.deepcopy(min_cost)

    if A == min_cost:
        for i in range(N):
            for j in range(N):
                if i!=j:
                    for k in range(N):
                        if k!=i and k!=j:
                            if min_cost[i][j]==min_cost[i][k]+min_cost[k][j]:
                                ans[i][j] = 0
        print(sum([sum(i) for i in ans])//2)
    else:
        print(-1)

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

from collections import Counter

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

Pre = [[[] for _ in range(S+1)] for _ in range(N+1)]

Pre[0][0] = [0]

for i, a in enumerate(A):
    for j in range(S+1):
        if len(Pre[i][j]) > 0:
            Pre[i + 1][j] += Pre[i][j]
            if a + j <= S:
                for n in Pre[i][j]:
                    Pre[i + 1][j + a].append(n + 1)
ans = 0
Ans = Counter(Pre[N][S])
for key, value in Ans.items():
    ans += pow(2, N - key, mod) * value
    ans %= mod

print(ans % mod)

### FIXED CODE ###

import numpy as np

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
f = np.zeros(3100, np.int64)

ans = 0
f[0] = 1
for a in A:
    g = f.copy()
    f[a:] += g[:-a]
    f += g
    f %= mod

print(f[S])
### BUGGY CODE ###

import itertools

h, w, m = map(int,input().split())

h_dict = dict()
w_dict = dict()

targets = list()

for _ in range(m):
    temp_h, temp_w, = map(int,input().split())

    h_dict[temp_h] = h_dict.get(temp_h, default=0) + 1
    w_dict[temp_w] = w_dict.get(temp_w, default=0) + 1

    targets.append((temp_h, temp_w))

max_h = max(h_dict.values())
max_w = max(w_dict.values())

h_candidates = [k for k, v in h_dict.items() if v == max_h]
w_candidates = [k for k, v in w_dict.items() if v == max_w]

for temp_h, temp_w in itertools.product(h_candidates, w_candidates):
    if not ((temp_h, temp_w) in targets):
        print(h_dict[temp_h] + w_dict[temp_w])
        break
else:
    print(h_dict[temp_h] + w_dict[temp_w] - 1)

### FIXED CODE ###

h, w, m = map(int,input().split())

h_dict = dict()
w_dict = dict()

targets = list()

for i in range(m):
    temp_h, temp_w, = map(int,input().split())

    h_dict[temp_h] = h_dict.get(temp_h, default=0) + 1
    w_dict[temp_w] = w_dict.get(temp_w, default=0) + 1

    targets.append((temp_h, temp_w))

h_dict_values = list(h_dict.values())
w_dict_values = list(w_dict.values())

max_h = max(h_dict_values)
max_w = max(w_dict_values)

nh = h_dict_values.count(max_h)
nw = w_dict_values.count(max_w)

x = 0

for i in range(m):
    temp_h, temp_w = targets[i]
    if h_dict[temp_h]==max_h and w_dict[temp_w]==max_w:
        x += 1

ans = max_h + max_w

if x == nh * nw:
    ans -= 1

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

import sys

h, n = map(int, input().split())
magic = []
INF = 10 ** 9
for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))
ans = 0
dp = [float('inf')] * (h + 1)

sys.setrecursionlimit(10 ** 7)
# 入力: 体力, 出力: 魔力の最小値
def magic_cost(hp):
    if dp[hp] != float('inf'):
        return dp[hp]

    cost_min = float('inf')
    for a, b in magic:
        if a >= hp:
            cost = b
        else:
            cost = b + magic_cost(hp - a)
        cost_min = min(cost, cost_min)
    dp[hp] = cost_min
    return cost_min

print(magic_cost(h))

### FIXED CODE ###

h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))
### BUGGY CODE ###

import numpy as np
from collections import deque
H, W = map(int, input().split())
grid = np.zeros((H + 2, W + 2), dtype=int)
for i in range(H):
    grid[i+1][1:-1] = [1 if j == "." else 0 for j in input()]
grid=grid.tolist()
    
mod = 10**9+7
cost = [[0]*(W+2) for _ in range(H+2)]
seen = [[False]*(W+2) for _ in range(H+2)]

cost[1][1] = 1
seen[1][1] = True
node = deque([(1, 1)])
while node:
    x, y = node.popleft()
    c = cost[x][y]

    if grid[x+1][y] == 1:
        cost[x+1][y] += c
        cost[x+1][y] %= mod
        if not seen[x+1][y]:
            seen[x+1][y] = True
            node.append((x+1, y))

    if grid[x][y + 1] == 1:
        cost[x][y+1] += c
        cost[x][y+1] %= mod
        if not seen[x][y+1]:
            seen[x][y+1] = True
            node.append((x, y+1))


ans = cost[H][W]
print(ans)


### FIXED CODE ###

import numpy as np
from collections import deque
H, W = map(int, input().split())
grid = np.zeros((H + 2, W + 2), dtype=int)
for i in range(H):
    grid[i+1][1:-1] = [1 if j == "." else 0 for j in input()]
grid = grid.tolist()

mod = 10**9+7
cost = [[0]*(W+2) for _ in range(H+2)]

cost[1][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        c = cost[i][j]
        if grid[i+1][j]:
            cost[i+1][j] += c
            cost[i+1][j] %= mod
        if grid[i][j+1]:
            cost[i][j+1] += c
            cost[i][j+1] %= mod

ans = cost[H][W]
print(ans)
### BUGGY CODE ###

mod = 2019
s = input()
n = len(s)
w = 0
d = [0] * mod
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	w %= mod
	d[w] += 1
d[0] += 1
o = 0
for x in d:
	o += x * (x - 1) // 2
print(o)


### FIXED CODE ###

mod = 2019
s = input()
n = len(s)
w = 0
d = [0] * mod
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	p %= mod
	w %= mod
	d[w] += 1
d[0] += 1
o = 0
for x in d:
	o += x * (x - 1) // 2
print(o)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int,input().split()))
ans = A[0]


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



if ans > 10**18:
    print(-1)

else:
    print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from decimal import *
import numpy as np
input = stdin.readline
N = int(input())
A = list(map(Decimal,input().split()))
np_A = np.array(A)
ans = np_A[0]

zero_flag = False
if 0 in A:
    zero_flag = True

flag = True

for i in range(1, N, 1):
    ans = Decimal(ans)*Decimal(np_A[i])
    #print(ans)
    if ans > 10**18:
        flag = False
        break


if zero_flag == True:
    print(0)


else:
    if flag == False:
        print(-1)

    else:
        print(ans)
### BUGGY CODE ###


def main():
    n, a, b = map(int, input().split())
    flag = True
    res = n
    count = 0
    if a == 0:
        print(0)
        exit(0)
    count = res // (a + b)
    res = n - ( ( a + b ) * count )
    a_count = 0
    while True:
        if a_count == a or res == 0:
            break
        res -= 1
        a_count += 1
           
    print( a_count + a * count)
    
    


if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    n, a, b = map(int, input().split())
    res = n
    count = 0
    if a == 0:
        print(0)
        exit(0)
    count = res // (a + b)
    res = n - ( ( a + b ) * count )
    if a < res:
        print(a * (count + 1))
    else:
        print(a * count + res)
    


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

argN = int(input())
argS = input()
aryS = list(argS)

idxBorder = 0
ansMin = 1000000

for i in range(argN+1):
  if i == 0:
    #cntW1 = 0
    cntB1 = 0
  else:
    #cntW1 = aryS[:i].count(".")
    cntB1 = aryS[:i].count("#")

  if i == argN:
    cntW2 = 0
    #cntB2 = 0
  else:
    cntW2 = aryS[i:].count(".")
    #cntB2 = aryS[i:].count("#")
  #print(str(i) + "," + str(cntB1) + "," + str(cntW2))
  ansMin = min(ansMin,cntB1 + cntW2)
print(ansMin)

### FIXED CODE ###

argN = int(input())
aryS = list(input())

cnt = aryS.count(".") 
ans = cnt
for i in range(argN):
  if aryS[i] == ".":
    cnt -= 1
  elif aryS[i] == "#":
    cnt += 1

  if ans > cnt:
    ans = cnt

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

s=str(input())
se=set()
se.add((s))
n=len(s)
s_="0"+s
for i in range(n):
  for j in range(1,n-i):
    k=(s_[1:i+1]+s_[i+j+1:i:-1]+s_[i+j+2:]) 
    se.add(k)
print(len(se))

### FIXED CODE ###

s=str(input())
L=[0]*26
n=len(s)
for i in range(n):
  L[ord(s[i])-97]+=1
num=0
total=n*(n-1)//2 +1
for i in range(26):
  if L[i]>1:
    num+=L[i]*(L[i]-1)//2
print(total-num)
### BUGGY CODE ###

n=input()
a=list(map(int,input().split()))
result=[]
i=0
while i<len(a):
  if len(a)%2!=0:
    if i%2==0:
      result=[a[i]]+result
    else:
      result=result+[a[i]]
  else:
    if i%2==0:
      result=result+[a[i]]
    else:
      result=[a[i]]+result
  i=i+1

print(*result)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=a[::-2]+a[N%2::2]
print(*b)
### BUGGY CODE ###

N,K = map(int,input().split())
t,d = list(zip(*sorted([list(map(int,input().split())) for _ in range(N) ],key=lambda x: (-x[1],x[0]))))

def get_value(sushi):
    ret = 0
    var = set()
    for i in sushi:
        ret += d[i]
        var.add(t[i])
    l = len(var)
    return ret + l*l

sushi = set()
sushi = set([(i,sushi.add(i))[0] for i in range(N) if t[i] not in [t[j] for j in sushi]][:K])
sushi |= set(list(set(range(N))-sushi)[:K-len(sushi)])

while 1:
    tmp = sushi - {max(sushi)}
    tmp.add(min(set(range(N)) - tmp))
    if get_value(tmp) <= get_value(sushi):
        break
    else:
        sushi = tmp
print(get_value(sushi))

### FIXED CODE ###

N,K = map(int,input().split())
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
sum_head = sum(head)
sum_no_head = sum(no_head)
sum_unused_head = 0
l_head = len(head)
l_no_head = len(no_head)
ans = sum_head + sum_no_head + l_head ** 2
for i in range(n):
    sum_no_head -= no_head[-1-i]
    sum_unused_head += unused_head[i]
    ans = max(ans,sum_head+sum_no_head+sum_unused_head + (l_head+i+1)**2)
print(ans)