题目描述

$\text{Turing}$ 学校售卖三种棒棒糖：崽崽棒、真枝棒和阿尔杯撕。它们的单价分别是 $a,b,c$ 元。小瓜拿着 $n$ 元钱购买一支棒棒糖，并由前台工作人员为他找零。前台只准备了 $1$ 元、$3$ 元和 $10$ 元三种硬币，每种硬币都有无限多个。请你寻找一个最佳找零方案，使得找回的硬币总数最少。

输入格式

第一行：四个整数 $a,b,c,n$，含义与题目中相同。

第二行：一个字符，表示购买的棒棒糖种类，x 表示崽崽棒，y 表示真枝棒，z 表示阿尔杯撕。

输出格式

一个整数，表示找回硬币的最少数量。

3 6 7 20
x

4

3 6 7 20
y

3

3 6 7 20
z

2

样例 $1$ 解释

支付了 $20$ 元购买了崽崽棒，崽崽棒的单价是 $3$ 元，因此需要找回 $17$ 元。凑成 $17$ 元所需硬币最少的方案是：$1$ 枚 $10$ 元，$2$ 枚 $3$ 元，$1$ 枚 $1$ 元，总共 $4$ 枚硬币。

数据范围

对于 $50\%$ 的数据，$1≤a,b,c≤n≤100$；

对于 $100\%$ 的数据，$1≤a,b,c≤n≤10^{9}$。