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

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    maxv=sum(v)+1
    dp=[[2**60]*maxv for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(maxv):
            if j>=v[i]:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j]=dp[i][j]

    ans=0
    for j in range(maxv):
        if W >= dp[N][j]:
            ans=j
    print(ans)
    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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    maxv=sum(v)+1
    dp=[[2**60]*maxv for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(maxv):
            if j>=v[i]:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j]=dp[i][j]

    ans=0
    for j in range(maxv):
        if W >= dp[N][j]:
            ans=j
    print(ans)
    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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

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

import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[0]*N
def f(x):
    if len(table[x])==0:
        return
    for i in table[x]:
        dp[i]=max(dp[x]+1,dp[i])
        f(i)
    return
for i in H:
    f(i)
print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[-1]*N
def f(x):
    if dp[x]!=-1:
        return dp[x]
    if len(table[x])==0:
        return 0
    t=0
    for i in table[x]:
        t=max(t,f(i)+1)
    dp[x]=t
    return t
for i in H:
    f(i)
print(max(dp))
### BUGGY CODE ###

from collections import deque
from sys import maxsize
from copy import deepcopy


class Graph:
    def __init__(self, No_of_nodes):
        self.n = No_of_nodes
        self.adj = [[] for i in range(self.n)]

    def addEdge(self, a, b, w):
        self.adj[a].append([b, w])

    def dijkstra(self, start):
        nxtpoint = [None for i in range(self.n)]
        distance = [maxsize for i in range(self.n)]
        distance[start] = 0
        q = deque()
        q.append(start)
        while len(q) != 0:
            a = q.pop()
            for u in self.adj[a]:
                b, w = u
                if distance[a] + w < distance[b]:
                    distance[b] = distance[a] + w
                    nxtpoint[b] = a
                    q.append(b)
        return nxtpoint


n, m = map(int, input().split())
ls = []
g = Graph(n)
ans = 'Yes\n'
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g.addEdge(a, b, 1)
    g.addEdge(b, a, 1)
point = g.dijkstra(0)
for i in range(1,n):
    if point[i] is None:
        ans = 'No'
        break
    else:
        ans += str(point[i] + 1) +'\n'
print(ans)


### FIXED CODE ###

from collections import deque
from sys import maxsize
from copy import deepcopy


class Graph:
    def __init__(self, No_of_nodes):
        self.n = No_of_nodes
        self.adj = [[] for i in range(self.n)]

    def addEdge(self, a, b, w):
        self.adj[a].append([b, w])

    def BFS(self, start):
        visited = [False] * self.n
        depth = [0 for i in range(self.n)]
        que = deque()
        q = [start]
        que.append(start)
        visited[start] = True
        ans = ''
        f = 0
        while que:
            s = que.popleft()
            ans += str(s) + ' '
            for i in self.adj[s]:
                if not visited[i[0]]:
                    depth[i[0]] = s
                    que.append(i[0])
                    visited[i[0]] = True
        return depth

    def dijkstra(self, start):
        nxtpoint = [None for i in range(self.n)]
        distance = [maxsize for i in range(self.n)]
        distance[start] = 0
        q = deque()
        q.append(start)
        while len(q) != 0:
            a = q.pop()
            for u in self.adj[a]:
                b, w = u
                if distance[a] + w < distance[b]:
                    distance[b] = distance[a] + w
                    nxtpoint[b] = a
                    q.append(b)
        return nxtpoint


n, m = map(int, input().split())
ls = []
g = Graph(n)
ans = 'Yes\n'
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g.addEdge(a, b, 1)
    g.addEdge(b, a, 1)
point = g.BFS(0)
for i in range(1, n):
    if point[i] is None:
        ans = 'No'
        break
    else:
        ans += str(point[i] + 1) + '\n'
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
city = [[0] for _ in range(n)]
cnt = [0] * n
buffer = []

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

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

for i in range(m):
    p, y = buffer[i]
    cnt[p - 1] += 1
    print(str(p).zfill(6) + str(city[p - 1].index(y)).zfill(6))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
l = []
num = [0] * n
ans = [""] * m

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

l.sort()


for p, y, i in l:
    num[p - 1] += 1
    ans[i] = str(p).zfill(6) + str(num[p - 1]).zfill(6)

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

n=int(input())
a=list(int(input()) for i in range(n))
b=[0]
c=[0]
for i in range(n):
    b.append(max(a[:i+1]))
    c.append(max(a[n-i-1:]))
del b[n]
del c[n]

for i in range(n):
    d=b[i]
    e=c[n-1-i]
    print(max(d,e))

### FIXED CODE ###

n=int(input())
a=list(int(input()) for i in range(n))
b=[0]
c=[0]
for i in range(n):
    b.append(max(b[i],a[i]))
    c.append(max(c[i],a[-i-1]))
del b[n]
del c[n]
 
for i in range(n):
    d=b[i]
    e=c[n-1-i]
    print(max(d,e))
### BUGGY CODE ###

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

B = 0

for i in range(N):
    B += 1
    for j in range(1,N-1):
        if i == j+1:
            break
        if S[i] == S[i-j]:
            B -= 1
            break

print(B)


### FIXED CODE ###

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

S_set = list(set(S))



print(len(S_set))
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
#print(L)

answer=0
for i in range(N-2):
  index_c=i+2
  for j in range(i+1,N-1):
    for k in range(index_c,N):
      if L[i]+L[j]<=L[k]:
        #print(i,j,k-1,k-j-1)
        answer+=k-j-1
        index_c=k-1
        break
    else:
      #print(i,j,N-1,N-j-1)
      answer+=N-j-1
      index_c=N-1
        
print(answer)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
#print(L)

answer=0
for i in range(N-2):
  index_c=i+2
  for j in range(i+1,N-1):
    for k in range(index_c,N):
      if L[i]+L[j]<=L[k]:
        #print(i,j,k-1,k-j-1)
        answer+=k-j-1
        index_c=k-1
        break
    else:
      #print(i,j,N-1,N-j-1)
      answer+=N-j-1
      index_c=N-1
        
print(answer)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
if N & 1:
    if A.count(0) == 1:
        for i in range(2,N,2):
            if A.count(i)!=2:
                print(0)
                exit()
    else:
        print(0)
        exit()
else:
    for i in range(1, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
print(pow(2, N//2, 10**9+7))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
if N & 1:
    if A[0] == 0:
        for i in range(1, N, 2):
            if A[i] != (i+1):
                print(0)
                exit()
    else:
        print(0)
        exit()
else:
    for i in range(0, N, 2):
        if A[i] != (i+1):
            print(0)
            exit()
print(pow(2, N//2, 10**9+7))
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))

#l,r,u,d = [[[0 for w in range(W)] for h in range(H)] for _ in range(4)]
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for h in range(H):
  for w in range(W):
    s = S[h][w]
    l[h][w] = (l[h][w-1]+1)*S[h][w]
    r[h][-w-1] = (r[h][-w]+1)*S[h][-w-1]
    u[h][w] = (u[h-1][w]+1)*S[h][w]
    d[-h-1][w] = (d[-h][w]+1)*S[-h-1][w]
  
#ans = 0
#for h in range(H):
#  for w in range(W):
#    tmp =(l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)*S[h][w]
#    ans = max(ans, tmp)
ans = np.max((l+r+u+d-3)*S)

print(ans)
    




### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d,dp):
    h=bl(dp,a[c])
    q=dp[::]
    q[h]=a[c]
    b[c]=bl(q,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c,q)
f(0,-1,dp)
for i in b:
    print(i)

### FIXED CODE ###

from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d):
    h=bl(dp,a[c])
    g=dp[h]
    dp[h]=min(dp[h],a[c])
    b[c]=bl(dp,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c)
    dp[h]=g
f(0,-1)
for i in b:
    print(i)
### BUGGY CODE ###

import math
k=int(input())
sum=0
for l in range(1,k+1):
    for m in range(1,k+1):
        for n in range(1,k+1):
            sum += math.gcd(math.gcd(l,m),n)

print(sum)

### FIXED CODE ###

from fractions import gcd
k=int(input())
l=[]
dp=[[0]*(k+1) for i in range(k+1)]

for i in range(1,k+1):
    for j in range(1,k+1):
        dp[i][j]=gcd(i,j)
        l.append(gcd(i,j))
sum=0
for x in range(1,k+1):
    for y in range(len(l)):
        sum += int(dp[l[y]][x])
print(sum)
### BUGGY CODE ###

mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

up=1
down=1
for i in range(1,b+1):
	up*=(n-i+1)
	down*=i
	if i==a:
		upa=up
		downa=down

nca=(upa%mod)*pow(downa,mod-2,mod)%mod
ncb=(up%mod)*pow(down,mod-2,mod)%mod
print((res-nca-ncb)%mod)

### FIXED CODE ###

mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

ncb=1
for i in range(1,b+1):
	ncb*=(n-i+1)*pow(i,mod-2,mod)
	ncb%=mod
	if i==a:
		nca=ncb
		
print((res-nca-ncb)%mod)
### BUGGY CODE ###

N = int(input())
S = input()
exc = 0

for i in range(N - 2):
    for j in range(1, N - 1):
        k = j + (j - i)
        if i > j or k < 2 or N - 1 < k:
            continue
        if S[k] != S[i] and S[k] != S[j] and S[i] != S[j]:
            exc += 1

ans = S.count("R") * S.count("G") * S.count("B") - exc
print(ans)


### FIXED CODE ###

N = int(input())
S = [s for s in input()]
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if N - 1 < k:
            continue
        if S[k] != S[i] and S[k] != S[j] and S[i] != S[j]:
            ans -= 1

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

import itertools

H,W = map(int,input().split())
cost = [list(map(int,input().split())) for _ in range(10)]
A = [list(map(int,input().split())) for _ in range(H)]


to1 = [10**3 for i in range(10)]

nlist = [0] + [i for i in range(2,10)]

for i in range(1,10):
    for v in itertools.permutations(nlist,i):
        c = 0
        for j in range(i-1):
            c += cost[v[j]][v[j+1]]
        c += cost[v[i-1]][1]
        to1[v[0]] = min(to1[v[0]], c)

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != 1 and A[h][w] != -1:
            ans += to1[A[h][w]]

print(ans)

        


### FIXED CODE ###

import itertools

H,W = map(int,input().split())
cost = [list(map(int,input().split())) for _ in range(10)]
A = [list(map(int,input().split())) for _ in range(H)]


to1 = [10**3 for i in range(10)]

nlist = [0] + [i for i in range(2,10)]

for i in range(1,10):
    for v in itertools.permutations(nlist,i):
        c = 0
        for j in range(i-1):
            c += cost[v[j]][v[j+1]]
        c += cost[v[i-1]][1]
        to1[v[0]] = min(to1[v[0]], c)

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != 1 and A[h][w] != -1:
            ans += to1[A[h][w]]

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

# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] # 試合グラフ
indegree = [0 for i in range((N * (N - 1)) // 2)] # 入次数
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    # i と a - 1の試合
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)
# この頂点からスタートしてBFSで、同じ頂点は通らないようにして移動
# 行けない場所があったら閉路あり
if len(stack) == 0:
  print(-1)
  exit(0)
  
from collections import deque
q = deque(stack)
visited = set()
while q:
  v = q.popleft()
  if v in visited:
    continue
  visited.add(v)
  for child in G[v]:
    q.append(child)

if len(visited) != (N * (N - 1)) // 2:
  print(-1)
  exit(0)

# stackに入った頂点からスタートしてグラフの最長経路を求める
# 閉路なしなので、より長い道があれば更新

stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append([i,1])

dist = [0 for i in range((N * (N - 1)) // 2)]
while stack:
  v, d = stack.pop()
  if dist[v] >= d:
    continue
  dist[v] = d
  for child in G[v]:
    stack.append([child, d + 1])
  
print(max(dist))


### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

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

count = 0
count1 = 0
for i in range(0,n,2):
    count = max(count, v.count(v[i]))
for j in range(1,n,2):
    count1 = max(count1, v.count(v[j]))
print(n//2 if len(set(v)) == 1 else n-count-count1)

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
a = Counter(v[::2])
b = Counter(v[1::2])
count = a.most_common()
count1 = b.most_common()
if len(set(v)) == 1:
    print(n//2)
    exit()
if count[0][0] == count1[0][0]:
    print(n- count[0][1] - (max(count[1][1], count1[1][1])))

else:
    print(n - count[0][1] - count1[0][1])
### BUGGY CODE ###

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    t = 0
    for ai, a in enumerate(L):
        for bi, b in enumerate(L[ai + 1:], ai + 1):
            ab = a + b
            lo = bi
            hi = len(L) - 1
            while lo != hi:
                mid = (lo + hi + 1) // 2
                if L[mid] < ab:
                    lo = mid
                else:
                    hi = mid - 1
            t += hi - bi
    print(t)


main()


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    t = 0
    l = len(L) - 1
    for ai, a in enumerate(L):
        ci = ai + 1
        for bi, b in enumerate(L[ai + 1:], ai + 1):
            ci = bisect.bisect_left(L, a + b, ci) - 1
            t += ci - bi
    print(t)


main()
### BUGGY CODE ###

S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        n = (d*e)%13
        r += dp[i][(j+13-n)%13]
      dp[i+1][j] = r%1000000007
  else:
    d = int(c)
    n = (d*e)%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  #print(dp[i+1])
print(dp[len(S)][5])


### FIXED CODE ###

S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]
#print(dp[0])
for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  #print(dp[i+1])
  dp.append(dpn)
print(dp[len(S)][5])
### BUGGY CODE ###

h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    queue = [start]
    depth = 0
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check[x][y] = True
        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if not check[t[0]][t[1]]:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    check[start[0]][start[1]] = True
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

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

def main():
    from sys import stdin
    readline = stdin.readline

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

    t = [[0] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        L, R = map(int, readline().split())
        t[L][R] += 1

    for i in range(N + 1):
        ti = t[i]
        for j in range(N):
            ti[j + 1] += ti[j]

    result = []
    for _ in range(Q):
        p, q = map(int, readline().split())
        result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
    print('\n'.join(str(v) for v in result))


main()


### FIXED CODE ###

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

t = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    t[L][R] += 1

for i in range(N + 1):
    for j in range(N):
        t[i][j + 1] += t[i][j]

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
print('\n'.join(str(v) for v in result))
### BUGGY CODE ###


iN , iK = [int(x) for x in input().split()]

iULimit = int( iN * 2  / iK )
iCount = 0
for i in range(1,iULimit+1):
    for j in range(1,iULimit + 1):
        for m in range(1,iULimit + 1):
            if( 0 < i + j - m and 0 < i -j + m and 0 < -i + j + m and i + j - m <= iULimit and i-j+m <= iULimit and -i+j+m <= iULimit):
                if( (i + j - m ) * iK % 2 == 0 and (i -j + m) * iK % 2 == 0 and ( -i + j + m) * iK % 2 ==0 ):
                    iCount = iCount + 1
print (iCount)


### FIXED CODE ###


iN , iK = [int(x) for x in input().split()]

if iK % 2 == 0 :
    iFK = int(iK / 2)
    # iFK の奇数だけの組と偶数だけの組
    iULimit = int(iN /iFK)
    if iULimit % 2 == 0:
        print (int(iULimit / 2 ) ** 3 * 2 )
    else:
        print( int((iULimit + 1 )/ 2) ** 3 + int((iULimit - 1)/2) ** 3)
else:
    #iKの倍数だけの組み合わせ
    iULimit = int( iN / iK )
    print(iULimit ** 3)