← 返回题目列表

AtCoder · abc438_b

D. 子串 2

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

给你整数 N 和 M,一个数字字符串 S 长度 N和一个数字字符串 T 长度 M。这里,数字字符串是由以下数字组成的字符串 0 to 9.

您可以执行以下操作零次或多次:

  • 从以下位置选择一个字符 T 并将所选数字增加 1。但是,如果选择的数字是 9,将其更改为 0.

找出完成该操作所需的最少操作数 T 一个子字符串 (连续 子序列) S.

约束

  • 1\le M\le N\le 100
  • N 和 M 是整数。
  • S 是长度为的数字字符串 N.
  • T 是长度为的数字字符串 M.

输入

输入由标准输入按以下格式给出:

N M
S
T

输出

输出完成所需的最少操作数 T 的子串 S.


示例输入 1

4 2
2025
91

示例输出 1

2

你可以使 T 的子串 S 有两个操作如下:

  • 对 2第一个字符 T. T= 91 变为 T= 92.
  • 对 1st 字符 T. T= 92 变为 T= 02.

02 是来自 2第一个字符 3rd 字符 S.

不可能使 T 的子串 S 少于两次操作,因此输出 2.


示例输入 2

3 2
438
38

示例输出 2

0

38 是一个子串 438 从头开始。因此,输出 0.


示例输入 3

5 5
00000
11111

示例输出 3

45

示例输入 4

8 3
20251227
438

示例输出 4

13