CodeEff/ECCO huggingface dataset:
# Original solution
class Process(object):
    def __init__(self, name, s):
        self.name = name
        self.s = s

    def exec(self, q):
        if self.s <= q:
            time = self.s
            self.s = 0
            return time
        else:
            time = q
            self.s = self.s - q
            return time

def execute(processes, q):
    time = 0
    completed = []
    while len(processes) != len(completed):
        for i, p in enumerate(processes):
            if not p.s == 0:
                time += p.exec(q)
                if p.s == 0:
                    completed.append((p, time))
    return completed

def run():
    n, q = list(map(int, input().split()))
    processes = []
    for _ in range(n):
        name, time = input().split()
        processes.append(Process(name, int(time)))
    completed = execute(processes, q)
    for c in completed:
        print(c[0].name, c[1])

if __name__ == '__main__':
    run()




# Optimized solution
class Process(object):
    def __init__(self, name, s):
        self.name = name
        self.s = s

    def exec(self, q):
        if self.s <= q:
            time = self.s
            self.s = 0
            return time
        else:
            time = q
            self.s = self.s - q
            return time

def execute(processes, q):
    time = 0
    completed = []
    while processes:
        p = processes.pop()
        time += p.exec(q)
        if p.s == 0:
            completed.append((p, time))
        else:
            processes.insert(0, p)
    return completed

def run():
    n, q = list(map(int, input().split()))
    processes = []
    for _ in range(n):
        name, time = input().split()
        processes.append(Process(name, int(time)))
    processes.reverse()
    completed = execute(processes, q)
    for c in completed:
        print(c[0].name, c[1])

if __name__ == '__main__':
    run()
# Original solution
def search(N, M, adj):
    reachable = [[set() for i in range(N)] for _ in range(N)]
    reachable[0] = adj
    start = -1
    for m in range(1, N):
        prev = reachable[m-1]
        cur = reachable[m]
        for i in range(N):
            cur[i] = set(prev[i])
        for i in range(N):
            for nxt in adj[i]:
                if i in prev[nxt]:
                    return (i, reachable, m+1)
                for p in prev[nxt]:
                    cur[i].add(p)
    return None


def main():
    N, M = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = list(map(int, input().split()))
        adj[A-1].add(B-1)
    result = search(N, M, adj)
    if not result:
        print((-1))
        return
    start, reachable, cnt = result
    ans = [-1] * cnt
    x = start
    for i in range(cnt):
        ans[i] = x+1
        for nxt in adj[x]:
            if start in reachable[cnt-i-1][nxt]:
                x = nxt
                break
    print((len(ans)))
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


# Optimized solution
def search(N, M, adj):
    reachable = [[set() for i in range(N)] for _ in range(N)]
    reachable[0] = adj
    start = -1
    for m in range(1, N):
        prev = reachable[m-1]
        cur = reachable[m]
        #        for i in range(N):
        #            cur[i] = set(prev[i])
        for i in range(N):
            for nxt in adj[i]:
                for p in prev[nxt]:
                    cur[i].add(p)
                if i in prev[nxt]:
                    return (i, reachable, m+1)
    return None


def main():
    N, M = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = list(map(int, input().split()))
        adj[A-1].add(B-1)
    result = search(N, M, adj)
    if not result:
        print((-1))
        return
    start, reachable, cnt = result
    ans = [-1] * cnt
    x = start
    for i in range(cnt):
        ans[i] = x+1
        for nxt in adj[x]:
            if start in reachable[cnt-i-2][nxt]:
                x = nxt
                break
    print((len(ans)))
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline
def main():
    n,m = list(map(int,input().split()))
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = list(map(int,input().split()))
        edge[a-1].append(b-1)


    new = [tuple([i]) for i in range(n)]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print((len(el)+1))
                        for e in el:
                            print((e+1))
                        print((go+1))

                        exit()
                    tank.append(el+(go,))
        new = tank
        
    print((-1))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
input = sys.stdin.readline
def main():
    n,m = list(map(int,input().split()))
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = list(map(int,input().split()))
        edge[a-1].append(b-1)


    new = [0]*n
    for i in range(n):
        new[i] = [i]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print((len(el)+1))
                        for e in el:
                            print((e+1))
                        print((go+1))

                        exit()
                    tank.append(el+[go])
        new = tank
        
    print((-1))

if __name__ == '__main__':
    main()
# Original solution
from collections import deque

     
def dfs(N, AB):
    status = [-1] * N
    for i in range(N):
        if status[i] == 1:
            continue
        stack = [i]
        status[i] = 0
        while stack:
            v = stack[-1]
            if AB[v]:
                n = AB[v].popleft()
                if status[n] == -1:
                    stack.append(n)
                    status[n] = 0
                else:
                    if n in stack:
                        idx = stack.index(n)
                        cycle = stack[idx:]
                        return cycle
            else:                  
                status[v] = 1
                stack.pop()
    return False


def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].popleft()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle


N, M = [int(i) for i in input().split()]
AB = [deque() for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)
                      
cycle = dfs(N, AB)
if not cycle:
    print((-1))
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print((len(cycle)))
    for v in cycle:
        print((v + 1))

# Optimized solution
def dfs(N, AB):
    status = [-1] * N
    for i in range(N):
        if status[i] == 1:
            continue
        stack = [i]
        status[i] = 0
        while stack:
            v = stack[-1]
            if AB[v]:
                n = AB[v].pop()
                if status[n] == -1:
                    stack.append(n)
                    status[n] = 0
                elif status[n] == 0:
                    idx = stack.index(n)
                    cycle = stack[idx:]
                    
                    return cycle
            else:                  
                status[v] = 1
                stack.pop()

    return False


def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle


N, M = [int(i) for i in input().split()]

AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)
                      
cycle = dfs(N, AB)
if not cycle:
    print((-1))
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print((len(cycle)))
    for v in cycle:
        print((v + 1))
# Original solution
from collections import deque


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

for _ in range(m):
    a, b = list(map(int, input().split()))
    edges[a - 1].append(b - 1)


def bfs(node):
    seen = [0] * n
    todo = deque([])
    for to in edges[node]:
        todo.append([to, 1, {to}])

    while todo:
        now, distance, path = todo.popleft()
        seen[now] = distance
        if now == node:
            return distance, path

        for next_node in edges[now]:  # type: int
            if seen[next_node] != 0:
                continue
            new_path = path | {next_node}
            todo.append([next_node, distance + 1, new_path])

    return float('INF'), set()


cycle_size = [float('INF')] * n
cycle_nodes = [set()] * n

for i in range(n):
    cycle_size[i], cycle_nodes[i] = bfs(i)

mini_cycle = min(cycle_size)
if mini_cycle == float('INF'):
    print((-1))
else:
    idx = cycle_size.index(mini_cycle)
    ans = cycle_nodes[idx]
    print(mini_cycle)
    for node in ans:
        print((node+1))


# Optimized solution
n, m = list(map(int, input().split()))
edges = [[] for _ in range(n)]

for _ in range(m):
    a, b = list(map(int, input().split()))
    edges[a-1].append(b-1)


def get_first_cycle(n, edges):
    seen = [-1] * n  # seen: -1: 未確認, 0: 非cycleのnode, 1: cycle候補
    for start in range(n):
        if seen[start] == 0:
            continue
        seen[start] = 1
        path = [start]
        while path:
            now = path[-1]
            if not edges[now]:
                path.pop()
                seen[now] = 0
                continue

            next_node = edges[now].pop()
            if seen[next_node] == -1:
                path.append(next_node)
                seen[next_node] = 1

            elif seen[next_node] == 1:
                idx = path.index(next_node)
                cycle = path[idx:]
                return cycle
    return False


cycle = get_first_cycle(n, edges)
if not cycle:
    print((-1))
    exit()

nodes = set(cycle)
length = len(cycle)
i = 0
while i < length:
    now = cycle[i]
    routes = edges[now]
    while routes:
        to = routes.pop()
        if to in nodes:
            update = True
            idx = cycle.index(to)
            cycle = cycle[:i+1] + cycle[idx:]
            nodes = set(cycle)
            length = len(cycle)
            break
    i += 1

print((len(cycle)))
for node in cycle:
    print((node+1))
# Original solution
def dfs(N, AB):
  status = [-1] * N
  for i in range(N):
      if status[i] == 1:
          continue
      stack = [i]
      status[i] = 0
      while stack:
          print(("stack:", stack))
          v = stack[-1]
          if AB[v]:
              n = AB[v].pop()
              if status[n] == -1:
                  stack.append(n)
                  status[n] = 0
              elif status[n] == 0:
                  idx = stack.index(n)
                  print(("stack:", stack, "n:", n, "idx:", idx))
                  cycle = stack[idx:]
                  
                  return cycle
          else:                  
              status[v] = 1
              stack.pop()
 
  return False

def dfs_2(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      # print("stack:", stack)
      curr, visited = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return visited
      else:
        # print("adding in visited:", curr)
        for i in AB[curr]:
          stack.append((i, visited+[curr]))
  return False

 
 
def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle
 
 
N, M = [int(i) for i in input().split()]
 
AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)

# print("AB:")
# for i in AB:
#   print(i)
cycle = dfs_2(N, AB)
# print("cycle:", cycle)
if not cycle:
    print((-1))
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print((len(cycle)))
    for v in cycle:
        print((v + 1))

# Optimized solution
def find_cycle(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      # print("stack:", stack)
      curr, visited = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return visited
      else:
        # print("adding in visited:", curr)
        for i in AB[curr]:
          stack.append((i, visited+[curr]))
  return False

 
 
def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle
 
 
N, M = [int(i) for i in input().split()]
 
AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)

cycle = find_cycle(N, AB)
# print("cycle:", cycle)
if not cycle:
    print((-1))
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print((len(cycle)))
    for v in cycle:
        print((v + 1))
# Original solution
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

for s in range(N):
    states_pool = deque()
    states_pool.append((s,set({}),set(range(N))-set({s})))
    while states_pool:
        u, chain, remain = states_pool.pop()
        if s in uv[u] and len(chain):
            print((len(chain)+1))
            for c in chain:
                print((c+1))
            print((u+1))
            exit()
        else:
            new_remain = remain.copy()
            if u != s: new_remain -= vu[u]
            candidates = new_remain & uv[u]
            new_remain -= uv[u]
            new_chain = chain.copy()
            new_chain.add(u)
            for c in candidates:
                states_pool.append((c, new_chain, new_remain))
    for i in range(s+1,N):
        uv[i].discard(s)
print((-1))

# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

EMPTY, LOOP, TREE = 0, 1, 2
ENTER, EXIT = 0, 1
status = [EMPTY] * N
for s in range(N):
    states_pool = [(s,[],ENTER)]
    while states_pool:
        u, chain, flag = states_pool.pop()
        if flag == EXIT or status[u] == TREE:
            status[u] = TREE
            continue
        elif status[u] == LOOP:
            break
        else: # ENTER, EMPTY
            status[u] = LOOP
            states_pool.append((u,chain,EXIT))
            new_chain = chain.copy()
            new_chain.append(u)
            for c in uv[u]:
                states_pool.append((c, new_chain, ENTER))
    else:
        continue
    break
else:
    print((-1))
    exit()

n = 0
while chain[n] != u:
    n += 1
chain = chain[n:]
L = len(chain)
nextnode = [None]*N
for i in range(L-1):
    nextnode[chain[i]] = chain[i+1]
nextnode[chain[L-1]] = chain[0]
pos = [None]*N
for p in range(len(chain)):
    pos[chain[p]] = p
i = 0
while i < L:
    h = 1
    c = chain[(i+1)%L]
    for j in uv[chain[i % L]]:
        p = pos[j]
        if p is None:
            continue
        else:
            if (p-i)%L > h:
                h = (p-i)%L
                c = j
    nextnode[chain[i % L]] = c
    i += 1
    while chain[i % L] != c:
        pos[chain[i % L]] = None
        i += 1

loop = [c]
k = c
while nextnode[k] != c:
    k = nextnode[k]
    loop.append(k)
print((len(loop)))
for l in loop:
    print((l+1))
# Original solution
import collections as c
n,k=list(map(int,input().split()));a=c.Counter(list(map(int,input().split())))
print(([0,sum(sorted([i for i in list(a.values())])[:len(a)-k])][len(a)>k]))

# Optimized solution
import collections as c
n,k=list(map(int,input().split()));a=c.Counter(list(map(int,input().split())))
print(([0,sum(sorted([*list(a.values())])[:len(a)-k])][len(a)>k]))
# Original solution
n, k = (int(i) for i in input().split())
balls = list(int(i) for i in input().split())
ball_set = set(balls)
freqs = list(balls.count(i) for i in ball_set)
freqs.sort(reverse=True)
print((sum(freqs[k:])))


# Optimized solution
n, k = (int(i) for i in input().split())
balls = (int(i) for i in input().split())
freqs = {}
for ball in balls:
    freqs[ball] = freqs[ball] + 1 if ball in freqs else 1
freq_hist = list(freqs.values())
freq_hist.sort(reverse=True)
print((sum(freq_hist[k:])))
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
key = []
value = []
for i, j in sorted(list(c.items()), key=lambda x: x[1]):
  key.append(i)
  value.append(j)

print((sum(value[:(len(key)-k)])))

# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
cnts = []
for i, j in list(c.items()):
  cnts.append(j)

print((sum(sorted(cnts)[:-k])))
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
cnts = []
for i, j in list(c.items()):
  cnts.append(j)

print((sum(sorted(cnts)[:-k])))

# Optimized solution
from collections import Counter
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
cnts = list(Counter(a).values())
print((sum(sorted(cnts)[:-k])))
# Original solution
from collections import Counter
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
cnts = list(Counter(a).values())
print((sum(sorted(cnts)[:-k])))

# Optimized solution
from collections import Counter
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
cnts = list(Counter(a).values())
print((sum(sorted(cnts, reverse=True)[k:])))
# Original solution
#!/usr/bin/env python3
import sys
import collections

def solve(N: int, K: int, A: "List[int]"):
    a_counter = collections.Counter(A)
    if len(a_counter) <= K:
        print((0))
        return 

    values = sorted(list(a_counter.values()))
    answer = 0
    for i in range(len(a_counter)-K):
        answer += values[i]
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
from collections import Counter

def solve(N: int, K: int, A: "List[int]"):
    counter = list(Counter(A).values())
    counter.sort()

    if len(counter) <= K:
        print((0))
    else:
        need = len(counter)-K
        print((sum(counter[:need])))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()
# Original solution
from collections import Counter
N,K=list(map(int,input().split()))
a = list(map(int,input().split()))
d=Counter(a)
d=sorted(list(d.items()),key=lambda x:x[1])
ans=0
for i in range(len(d)-K):
        ans+=d[i][1]
print(ans)

# Optimized solution
from collections import Counter
N,K=list(map(int,input().split()))
a = list(map(int,input().split()))
d=Counter(a)
ans=sum(sorted(list(d.values()),reverse=1)[:K])
print((N-ans))
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
kind=[]
count=1
for i in range(len(a)-1):
  if(a[i]==a[i+1]):count+=1
  else:
    kind.append(count)
    count=1
kind.append(count)
kind.sort()
change=0
while(len(kind)>k):
  change+=kind.pop(0)
print(change)

# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
kind=[]
count=1
for i in range(len(a)-1):
  if(a[i]==a[i+1]):count+=1
  else:
    kind.append(count)
    count=1
kind.append(count)
kind.sort()
change=0
for i in range(k):
  if(len(kind)!=0):change+=kind.pop()
print((n-change))
# Original solution
import collections
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
ans=0
c=collections.Counter(a)
if len(c)<k:
    print(ans)
    exit()

for i in range(1,-k+len(c)+1):
    ans+=c.most_common()[-i][1]
print(ans)


# Optimized solution
import collections
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
ans=0
c=collections.Counter(a)
if len(c)<k:
    print(ans)
    exit()
l=c.most_common()
for i in range(1,-k+len(c)+1):
    ans+=l[-i][1]
print(ans)
# Original solution
nums , types = list(map(int, input().split()))
array = list(map(int,input().split()))
array.sort()
type_count = 0
count = 0
result = 0
ary_count = []
array.append(1000000000)

for i in range (nums):
    if array[i] == array[i +1]:
        count += 1
    elif array[i] < array[i +1]:
        ary_count.append(count)
        type_count += 1
        count = 0

if type_count > types:
    for i in range(type_count - types):
        result += min(ary_count)+1
        ary_count.pop(ary_count.index(min(ary_count)))

print(result)

# Optimized solution
nums , types = list(map(int, input().split()))
array = list(map(int,input().split()))
array.sort()
type_count = 0
count = 0
result = 0
ary_count = []
array.append(1000000000)

for i in range (nums):
    if array[i] == array[i +1]:
        count += 1
    elif array[i] < array[i +1]:
        ary_count.append(count)
        type_count += 1
        count = 0

ary_count.sort()

if type_count > types:
    for i in range(type_count - types):
        result += ary_count[i]+1
print(result)
# Original solution
from collections import Counter
N,K=list(map(int,input().split()))
A=input().split()
B=Counter(A)
C=sorted(list(B.items()),key=lambda x: -x[1])
print((sum(C[K:][i][1] for i in range(len(C[K:])))))

# Optimized solution
from collections import Counter
N,K=list(map(int,input().split()))
A=input().split()
B=Counter(A)
C=sorted(list(B.values()),reverse=True)
print((sum(C[K:])))