Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def main():
    mod = 1000000007
    n, k = (int(x) for x in input().split())
    l = (i for i in range(n + 1))  # おまけの小さい部分，でも大事

    # 累積和を計算しておく，前からと後ろから。
    former = 0
    acm = tuple((former:= former + i) for i in range(n + 1))
    former = 0
    acm_rev = tuple((former:= former + i) for i in range(n, -1, -1))

    ans = 0
    # 選ぶ数の数で分ける。でかい部分は無視して，
    # 最小値と最大値が分かれば取りうる値も分かる。
    for j in range(k-1, n + 1):
        ans += acm_rev[j] - acm[j] + 1
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():
    mod = 1000000007
    n, k = (int(x) for x in input().split())
    l = (i for i in range(n + 1))  # おまけの小さい部分，でも大事

    # 累積和を計算しておく，前からと後ろから。
    former = 0
    acm = tuple((former:= former + i) for i in range(n + 1))
    former = 0
    acm_rev = tuple((former:= former + i) for i in range(n, -1, -1))

    ans = 0
    # 選ぶ数の数で分ける。でかい部分は無視して，
    # 最小値と最大値が分かれば取りうる値も分かる。
    for j in range(k-1, n + 1):
        ans += acm_rev[j] - acm[j] + 1
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    mod = 1000000007
    n, k = (int(x) for x in input().split())
    l = tuple(i for i in range(n + 1))  # おまけの小さい部分，でも大事
    ans = 0
    # 選ぶ数の数で分ける。でかい部分は無視して，
    # 最小値と最大値が分かれば取りうる値も分かる。
    for j in range(k, n + 2):
        _min = sum(l[:j])
        _max = sum(l[-j:])
        ans += _max - _min + 1
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():
    mod = 1000000007
    n, k = (int(x) for x in input().split())
    l = (i for i in range(n + 1))  # おまけの小さい部分，でも大事

    # 累積和を計算しておく，前からと後ろから。
    former = 0
    acm = tuple((former:= former + i) for i in range(n + 1))
    former = 0
    acm_rev = tuple((former:= former + i) for i in range(n, -1, -1))

    ans = 0
    # 選ぶ数の数で分ける。でかい部分は無視して，
    # 最小値と最大値が分かれば取りうる値も分かる。
    for j in range(k-1, n + 1):
        ans += acm_rev[j] - acm[j] + 1
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    mod = 1000000007
    n, k = (int(x) for x in input().split())
    l = tuple(i for i in range(n + 1))  # おまけの小さい部分，でも大事
    ans = 0
    # 選ぶ数の数で分ける。でかい部分は無視して，
    # 最小値と最大値が分かれば取りうる値も分かる。
    for j in range(k, n + 2):
        _min = sum(l[:j])
        _max = sum(l[-j:])
        ans += _max - _min + 1
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():
    mod = 1000000007
    n, k = (int(x) for x in input().split())
    l = (i for i in range(n + 1))  # おまけの小さい部分，でも大事

    # 累積和を計算しておく，前からと後ろから。
    former = 0
    acm = tuple((former:= former + i) for i in range(n + 1))
    former = 0
    acm_rev = tuple((former:= former + i) for i in range(n, -1, -1))

    ans = 0
    # 選ぶ数の数で分ける。でかい部分は無視して，
    # 最小値と最大値が分かれば取りうる値も分かる。
    for j in range(k-1, n + 1):
        ans += acm_rev[j] - acm[j] + 1
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [0] * (k + 1)

for i in range(0, k + 1):
    d[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)


Fixed submission:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) for i in range(1, k + 1)]
d.insert(0, 0)

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Buggy python submission (verdict: Runtime Error):
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k, n, MOD) for i in range(1, k+1)]

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)


Fixed submission:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) for i in range(1, k + 1)]
d.insert(0, 0)

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
border = 10000
if k < border:
    candidate = 1
    count = 1
    while True:
        if count == k:
            print(candidate)
            break

        candidate += 1
        digits = tuple(int(c) for c in str(candidate))
        for i, d in enumerate(digits[:-1]):
            if abs(d - digits[i + 1]) > 1:
                break
        else:
            count += 1

else:
    candidate = 3234566667
    count = 100000
    while True:
        if count == k:
            print(candidate)
            break

        digits = tuple(int(c) for c in str(candidate))
        for i, d in enumerate(digits[:-1]):
            if abs(d - digits[i + 1]) > 1:
                break
        else:
            count -= 1

        candidate -= 1

# Candidate 100000 -> 3234566667


Fixed submission:
def main():
    k = int(input())
    lunluns = [i for i in range(1, 10)]
    if k <= len(lunluns):
        print(lunluns[k - 1])
        return

    while True:
        if k <= len(lunluns):
            print(lunluns[k - 1])
            return
        k -= len(lunluns)
        olds = lunluns
        lunluns = []
        for old in olds:
            for i in (-1, 0, 1):
                digit_next = old % 10 + i
                if digit_next < 0 or digit_next > 9:
                    continue
                new = old * 10 + digit_next
                lunluns.append(new)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
border = 10000
if k < border:
    candidate = 1
    count = 1
    while True:
        if count == k:
            print(candidate)
            break

        candidate += 1
        digits = tuple(int(c) for c in str(candidate))
        for i, d in enumerate(digits[:-1]):
            if abs(d - digits[i + 1]) > 1:
                break
        else:
            count += 1

else:
    candidate = 3234566667
    count = 100000
    while True:
        if count == k:
            print(candidate)
            break

        digits = tuple(int(c) for c in str(candidate))
        for i, d in enumerate(digits[:-1]):
            if abs(d - digits[i + 1]) > 1:
                break
        else:
            count -= 1

        candidate -= 1

# Candidate 100000 -> 3234566667


Fixed submission:
def main():
    k = int(input())
    lunluns = [i for i in range(1, 10)]
    if k <= len(lunluns):
        print(lunluns[k - 1])
        return

    while True:
        if k <= len(lunluns):
            print(lunluns[k - 1])
            return
        k -= len(lunluns)
        olds = lunluns
        lunluns = []
        for old in olds:
            for i in (-1, 0, 1):
                digit_next = old % 10 + i
                if digit_next < 0 or digit_next > 9:
                    continue
                new = old * 10 + digit_next
                lunluns.append(new)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# D - String Formation
# 2020-05-21 08:17


def main():
    s = input()
    n = int(input())
    for _ in range(n):
        query = input().split()
        if query[0] == '1':
            s = s[::-1]
        else:
            if query[1] == '1':
                s = query[2] + s
            else:
                s += query[2]
    return s


if __name__ == '__main__':
    print(main())


Fixed submission:
# D - String Formation
# 2020-05-21 08:17
from collections import deque


def main():
    chars = deque(input())
    chars_append = chars.append
    chars_appendleft = chars.appendleft
    n = int(input())
    direction = 1
    for _ in range(n):
        query = input().split()
        if query[0] == '1':
            direction *= (-1)  # reverse
        else:
            if query[1] == '1':
                # if head-adding: 1, tail: -1
                head = direction
            else:
                head = (-direction)
            if head == 1:
                chars_appendleft(query[2])
            else:
                chars_append(query[2])

    if direction == -1:
        chars.reverse()
    return ''.join(chars)


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs = combs % mod * i % mod * pow(j, mod - 2, mod) % mod
    return combs


def main():
    n, a, b = [int(x) for x in input().split()]
    combs = [0] * (n + 1)  # memorize
    combs[0] = 1  # Pick no flower
    ans = 0
    for pick in range(1, n + 1):
        tmp = combs[n - pick]
        if tmp != 0:
            comb = tmp
        else:
            comb = combinations_mod(n, pick)
        combs[pick] = comb
        if pick not in (a, b):
            ans += comb
            ans %= 1000000007

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs = combs % mod * i % mod * pow(j, mod - 2, mod) % mod
    return combs


def main():
    n, a, b = [int(x) for x in input().split()]
    mod = 1000000007
    total = pow(2, n, mod) - 1
    ans = total - combinations_mod(n, a) - combinations_mod(n, b)
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from itertools import accumlate


def main():
    n, k = [int(x) for x in input().split()]
    dice = [int(x) for x in input().split()]

    expected_accum = list(accumlate((1 + p) / 2 for p in dice))

    def gen():
        for start in range(n - k + 1):
            if start == 0:
                yield expected_accum[k - 1]
            else:
                yield expected_accum[start + k - 1] - expected_accum[start - 1]

    print(max(gen()))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, k = [int(x) for x in input().split()]
    dice = [int(x) for x in input().split()]

    expected_accum = []
    for i, p in enumerate(dice):
        ex = (1 + p) / 2
        if i == 0:
            expected_accum.append(ex)
        else:
            expected_accum.append(expected_accum[-1] + ex)

    def gen():
        for start in range(n - k + 1):
            if start == 0:
                yield expected_accum[k - 1]
            else:
                yield expected_accum[start + k - 1] - expected_accum[start - 1]

    print(max(gen()))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for d in range(60):
    ones = 0
    for a in l:
        if a >> d & 1:
            ones += 1
    zeroes = n - ones
    ans += pow(2, d, MOD) * ones % MOD * zeroes % MOD
ans %= MOD
print(ans)


Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)


Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

ind = int(input())
nums = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for v in itertools.combinations(nums, 2):
    # XOR は四則演算よりも優先度が低い…….
    ans = (ans + (v[0] ^ v[1])) % MOD

print(ans)


Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

ind = int(input())
nums = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for v in itertools.combinations(nums, 2):
    # XOR は四則演算よりも優先度が低い…….
    ans = (ans + (v[0] ^ v[1])) % MOD

print(ans)


Fixed submission:
n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    item_no, discount_no = [int(x) for x in input().split()]
    prices = [int(x) for x in input().split()]

    for _ in range(discount_no):
        prices.sort(reverse=True)
        prices[0] //= 2

    print(sum(prices))


if __name__ == '__main__':
    main()


Fixed submission:
# 解説を読んだ。優先度付きキューね，はい。
import heapq


def main():
    item_no, discount_no = [int(x) for x in input().split()]
    prices = [int(x) * -1 for x in input().split()]
    heapq.heapify(prices)

    for _ in range(discount_no):
        current_max = heapq.heappop(prices)
        current_max = current_max * -1 // 2 * -1
        heapq.heappush(prices, current_max)

    print(- sum(prices))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    platform_count, jumping_power = [int(x) for x in input().split()]
    platforms = [int(x) for x in input().split()]
    dp = [0]
    for i in range(1, platform_count):
        indexes = (i - x for x in range(1, jumping_power + 1) if i - x >= 0)
        dp.append(
            min(abs(platforms[i] - platforms[before]) + dp[before]
                for before in indexes))
    print(dp[platform_count - 1])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    platform_count, jumping_power = [int(x) for x in input().split()]
    platforms = [int(x) for x in input().split()]
    dp = [0]
    for i in range(1, platform_count):
        indexes = (i - x for x in range(1, jumping_power + 1) if i - x >= 0)
        dp.append(
            min(abs(platforms[i] - platforms[before]) + dp[before]
                for before in indexes))
    print(dp[platform_count - 1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    platform_count, jumping_power = [int(x) for x in input().split()]
    platforms = [int(x) for x in input().split()]
    INF = 10001
    dp = [INF] * platform_count
    dp[0] = 0
    for i in range(1, platform_count):
        indexes = (i - x for x in range(1, jumping_power + 1) if i - x >= 0)
        dp[i] = min(
            abs(platforms[i] - platforms[before]) + dp[before]
            for before in indexes)
    print(dp[platform_count - 1])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    platform_count, jumping_power = [int(x) for x in input().split()]
    platforms = [int(x) for x in input().split()]
    dp = [0]
    for i in range(1, platform_count):
        indexes = (i - x for x in range(1, jumping_power + 1) if i - x >= 0)
        dp.append(
            min(abs(platforms[i] - platforms[before]) + dp[before]
                for before in indexes))
    print(dp[platform_count - 1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main(a, b, c, x):

    def gen(coin, n_of_coins, x_parts):
        for x_part in x_parts:
            for i in range(n_of_coins + 1):
                new_x_part = x_part + coin * i
                yield new_x_part

    x_maybe_iter = gen(50, c, gen(100, b, gen(500, a, [0])))
    patterns = sum(x_maybe == x for x_maybe in x_maybe_iter)
    return patterns


if __name__ == '__main__':
    a, b, c, x = [int(input()) for _ in range(4)]
    print(main(a, b, c, x))


Fixed submission:
def main():
    x, a, b = [int(input()) for i in range(3)]
    ans = (x - a) % b
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    matrix = [list(map(int, list(input()))) for i in range(2)]

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    matrix = []
    matrix.append([int(num) for num in input().split()])
    matrix.append([int(num) for num in input().split()])

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    matrix = [list(map(int, list(input()))) for i in range(2)]

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    matrix = []
    matrix.append([int(num) for num in input().split()])
    matrix.append([int(num) for num in input().split()])

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    matrix = [int(num) for num in [input().split() for _ in range(2)]]

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    matrix = []
    matrix.append([int(num) for num in input().split()])
    matrix.append([int(num) for num in input().split()])

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    matrix = [int(num) for num in (input().split() for i in range(2))]

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    matrix = []
    matrix.append([int(num) for num in input().split()])
    matrix.append([int(num) for num in input().split()])

    candies = [sum(matrix[0][:d+1]) + sum(matrix[1][d:]) for d in range(n)]
    print(max(candies))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
6 6
#####.
#.#.##
####.#
.#..#.
#.##..
#.#...


Fixed submission:
h, w = [int(x) for x in input().split()]
matrix = [list(input()) for _ in range(h)]
surrounding_distances = (-1, 0, 1)


def count_bombs(i, j):
    for da in surrounding_distances:
        for db in surrounding_distances:
            if da == db == 0:
                # Not surrounidings.
                continue
            si = i + da
            sj = j + db
            if si < 0 or si >= h or sj < 0 or sj >= w:
                continue
            if matrix[si][sj] == '#':
                yield 1


for i in range(h):
    for j in range(w):
        if matrix[i][j] == '.':
            matrix[i][j] = str(sum(count_bombs(i, j)))

[print(''.join(row)) for row in matrix]
Buggy python submission (verdict: Time Limit Exceeded):
a, b, x = [int(x) for x in input().split()]
minimum, maximum = None, None

for i in range(a, b + 1):
    if i % x == 0:
        minimum = i
        break

for i in range(b, a - 1, -1):
    if i % x == 0:
        maximum = i
        break

if minimum != None or maximum != None:
    if minimum != None and maximum != None:
        # 普通の / 除算だと3で割ったときに大きくずれる。
        total = (maximum - minimum) // x + 1
    else:
        total = 1
else:
    total = 0

print(total)


Fixed submission:
def main(a, b, x):
    if x > b:
        return 0
    elif x == b:
        return 1

    minimum, maximum = None, None

    for i in range(a, b + 1):
        if i % x == 0:
            minimum = i
            break

    for i in range(b, a - 1, -1):
        if i % x == 0:
            maximum = i
            break

    if minimum != None or maximum != None:
        if minimum != None and maximum != None:
            # 普通の / 除算だと3で割ったときに大きくずれる。
            return (maximum - minimum) // x + 1
        else:
            return 1
    else:
        return 0


def main_b(a, b, x):
    """解説を読んだ。単純なことだった。
    """
    def count(n):
        if n == -1:
            return 0
        else:
            return n // x + 1

    return count(b) - count(a-1)


if __name__ == "__main__":
    a, b, x = [int(x) for x in input().split()]
    print(main_b(a, b, x))
Buggy python submission (verdict: Runtime Error):
a = input().spolit()

if int(a[0]) > int(a[1]):
  print("safe")
else:
  print("unsafe")

Fixed submission:
a = input().split()

if int(a[0]) <= int(a[1]):
  print("unsafe")
else:
  print("safe")
Buggy python submission (verdict: Runtime Error):
s = list(input())
t = list(input())

if(t in s):
    print(0)

result = []
for i in range(len(s) - len(t)):
    result.append(len(t))
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            result[i] -= 1

print(min(result))



Fixed submission:
s = list(input())
t = list(input())

if(t in s):
    print(0)

result = [0] * ((len(s) - len(t)) + 1)
for i in range(len(s) - len(t) + 1):
    result[i] = len(t)
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            result[i] -= 1
 
print(min(result))

Buggy python submission (verdict: Runtime Error):
s = list(input())
t = list(input())

result = []
for i in range(len(s) - len(t)):
    result.append(len(t))
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            result[i] -= 1

print(min(result))



Fixed submission:
s = list(input())
t = list(input())

if(t in s):
    print(0)

result = [0] * ((len(s) - len(t)) + 1)
for i in range(len(s) - len(t) + 1):
    result[i] = len(t)
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            result[i] -= 1
 
print(min(result))