题目描述

给定一个仅由小写字母构成的字符串 $s$，以及一个长度为 $26$ 的数组 ${\rm cnt}$，其中 ${\rm cnt}_i$ 表示第 $i$ 个字母（${\rm cnt}_0$ 表示字母 $\texttt{'a'}$、${\rm cnt}_1$ 表示字母 $\texttt{'b'}$、……、${\rm cnt}_{25}$ 表示字母 $\texttt{'z'}$ 的数量。

你需要使用 ${\rm cnt}$ 中的字符重新拼接出尽可能多的字符串，要求每个新字符串的字典序必须严格大于 $s$（${\rm cnt}$ 中的字符可以不用完）。

请计算最多能构造多少个这样的字符串。不要求互不相同，计数按构造的个数累加。

【名词解释】

字符串的字典序比较：从左到右逐个比较两个字符串的字符。如果在某个位置上字符不同，比较这两个字符的字母表顺序，字母序大的字符串字典序也大。如果一直比较到其中一个字符串结束，则较短的字符串字典序更小。

输入格式

第一行输入一个长度为 $|s|$ 的字符串 $s$。

第二行输入 $26$ 个整数 ${\rm cnt}_0,{\rm cnt}_1,\dots,{\rm cnt}_{25} \left(0 \leq {\rm cnt}_i \leq 10^9\right)$，代表每个字符还剩下多少个。

输出格式

输出一个整数，代表答案。

dcb
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2

fedcb
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

42

样例解释

在第一组样例中，给了 $\texttt{'a'}$、$\texttt{'b'}$、$\texttt{'c'}$、$\texttt{'d'}$、$\texttt{'e'}$ 字符各一个，可以构造出 $\texttt{"e"}$ 和 $\texttt{"dcba"}$ 两个字典序严格大于 $\texttt{"dcb"}$ 的字符串。

数据规模与约定

下发文件

下发文件对应子任务 $3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq |s| \leq 10^6,0 \leq cnt_i \leq 10^9$。保证 ${\rm cnt}_i$ 之和不超过 $10^9$。