CF1691C Sum of Substrings

给定由 $0$ 和 $1$ 组成的长度为 $n$ 的字符串 $ s $ 。 定义一个十进制数字 $ d_i $ 十位和个位分别为 $ s_i $ 和 $ s_{i+1} $ 。 定义 $ f(s) $ 为所有合法的 $ d_i $ 的和。也就是说 $ f(s) = \sum\limits_{i=1}^{n-1} d_i $ 。 比如， 对于字符串 $ s = 1011 $ ： - $ d_1 = 10 $ ； - $ d_2 = 01 $ ； - $ d_3 = 11 $ ; - $ f(s) = 10 + 01 + 11 = 22 $ 。 在一次操作中你可以交换两个相邻的元素。 找到经过不多于 $k$ 次操作后 $ f(s) $ 的最小值。 保证所有数据中 $ n $ 的和不超过 $ 10^5 $ 。

每个测试点有多组数据。 第一行一个整数 $t$ 表示数据个数。 接下来 $2t$ 行，每组数据 $2$ 行。 每组数据的第一行两个整数 $ n $ 和 $ k $ ( $ 2 \le n \le 10^5 $ , $ 0 \le k \le 10^9 $ ) ，分别表示字符串长度和最大操作数。

共 $t$ 行，每一行一个整数，表示经过不多于 $k$ 次操作后 $ f(s) $ 的最小值。

- 对于第一组数据，不能做任何操作。$ f(s) = f(1010) = 10 + 01 + 10 = 21 $ 。 - 对于第二组数据，可以将字符串变成 $0011000$。 此时 $ f $ 的值为 $ 22 $ 。 - 对于第三组数据，可以将字符串变成 $00011$。 此时 $ f $ 的值为 $ 12 $ 。