题目描述

小明最近迷上了字符串操作。对每个字符串，小明每次可以执行以下两种操作之一：

1. 把字符串的某个字符改成任意一个其他字符，花费 $1$ 的代价；
2. 交换字符串中的两个字符，花费 $0$ 的代价。

小明发现，把一个字符串通过一系列的操作，可以转换成任何一个与之等长的字符串。

例如，把 $\tt hello$ 变为 $\tt world$ 的一种代价为 $3$ 的操作序列如下： $\gdef\ar{\rightarrow}$

1. $\tt \red hello \ar \red wello$（替换 $\tt h$ 为 $\tt w$，代价为 $1$）。
2. $\tt w\blue ell\blue o\ar w\blue oll\blue e$（交换 $\tt e$ 和 $\tt o$，代价为 $0$）。
3. $\tt wo\red lle \ar wo\red rle$（替换 $\tt l$ 为 $\tt r$，代价为 $1$）。
4. $\tt worl\red e \ar worl\red d$（替换 $\tt e$ 为 $\tt d$，代价为 $1$）。

小明发现，无法用少于 $3$ 次的代价将 $\tt hello$ 变为 $\tt world$。

显然，不同的转换方案花费的代价是不同的，请编程帮助小明计算把一个字符串变为另一个字符串的最小代价。

输入格式

一行两个用空格隔开的正整数 $n$（字符串长度），$s_0$（数据生成器的初始数值）。

本题中的字符串根据给定的初始数值 $s_0$ 按以下规则生成：

$$\begin{aligned} &\text{for } i=1\text{ to } n\\ &\quad s_i\leftarrow(s_{i-1}\times345) \bmod 19997 \end{aligned} $$

第二个字符串的第 $i\in [1,n]$ 个字符的 ASCII 码为 $97+(s_i \bmod 26)$。

然后令 $t_0=s_n$。

$$\begin{aligned} &\text{for } i=1\text{ to } n\\ &\quad t_i\leftarrow(t_{i-1}\times345) \bmod 19997 \end{aligned} $$

第二个字符串的第 $i\in [1,n]$ 个字符的 ASCII 码为 $97+(t_i \bmod 26)$。

输出格式

一行一个非负整数，表示将第一个字符串转换为第二个字符串的最少代价。

4 35

2

100 31

29

提示

$1\le n\le 10^6,1\le s_0\le 19997$。

本题原始满分为 $20\text{pts}$。