B - Substring 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 N,M と長さ N の数字列 S 、長さ M の数字列 T が与えられます。ここで、数字列とは 0 から 9 までの数字のみから構成される文字列のことを表します。

あなたは以下の操作を 0 回以上好きな回数行うことができます：

  • T から 1 文字選び、選んだ数字を 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

以下のように 2 回操作することで T を S の部分文字列にすることができます。

  • T の 2 文字目に対して操作する。 T= 91 から T= 92 になる。
  • T の 1 文字目に対して操作する。 T= 92 から T= 02 になる。

02 は S の 2 文字目から 3 文字目までの部分文字列となっています。

2 回未満の操作で 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

Score : 200 points

Problem Statement

You are given integers N and M, a digit string S of length N, and a digit string T of length M. Here, a digit string is a string consisting of digits from 0 to 9.

You can perform the following operation zero or more times:

  • Choose one character from T and increase the chosen digit by 1. However, if the chosen digit is 9, change it to 0.

Find the minimum number of operations required to make T a substring (contiguous subsequence) of S.

Constraints

  • 1\le M\le N\le 100
  • N and M are integers.
  • S is a digit string of length N.
  • T is a digit string of length M.

Input

The input is given from Standard Input in the following format:

N M
S
T

Output

Output the minimum number of operations required to make T a substring of S.

Sample Input 1

4 2
2025
91

Sample Output 1

2

You can make T a substring of S with two operations as follows:

  • Perform the operation on the 2nd character of T. T= 91 becomes T= 92.
  • Perform the operation on the 1st character of T. T= 92 becomes T= 02.

02 is a substring from the 2nd character to the 3rd character of S.

It is impossible to make T a substring of S with less than two operations, so output 2.

Sample Input 2

3 2
438
38

Sample Output 2

0

38 is a substring of 438 from the beginning. Thus, output 0.

Sample Input 3

5 5
00000
11111

Sample Output 3

45

Sample Input 4

8 3
20251227
438

Sample Output 4

13