题目背景

demon最近沉迷于三角洲绝密航天跑刀，他想知道在 30 分钟之内如何能吃更多的物资。

航天的地图如下：

我们把他简化一下：

航天地图共有 A ～ J 十个物资点，A, B, C, I 为四个可能的出生点，J 为唯一的撤离点。开局默认先搜索出生点的物资，然后才能移动到相邻点位。

每个点位有 4 个物资，搜索需要 2 分钟。点位之间通过道路相连，每条道路通行时间为 0.5 分钟。

demon 必须在时间限制内到达 J 点撤离，否则就会被淘汰。他想知道：从不同的出生点出发，在给定的时间限制内，最多能搜到多少物资？

题目描述

地图为一个无向图，共 10 个节点（A ～ J），边如下：

A-B, A-D,
B-C, B-E, B-D,
C-H, C-J,
D-E, D-F, D-G,
E-H,
F-H,
G-I, G-H,
H-I,
I-J

每条边通行时间均为 0.5 分钟。

规则：

1. 开局后，先搜索出生点的物资（耗时 2 分钟，获得 4 物资）。
2. 移动到相邻未搜索过的点位时，搜索该点（耗时 2 分钟，获得 4 物资）。
3. 已经搜索过的点位可以再次经过，不再消耗搜索时间，也不再获得物资。
4. 必须在给定的时间限制内到达 J 点才算成功撤离。
5. 搜索时间和通行时间之和不得超过时间限制。

输入格式

一行，两个空格分隔的值：一个字符 S 和一个整数 T。

• S 表示出生点，$S ∈ (A, B, C, I)$。
• T 表示时间限制（分钟），$1 ≤ T ≤ 30$。

输出格式

一行，一个整数，表示在 T 分钟内能获得的最大物资数量。

样例

A 30

40

说明： 从 A 出发，时间限制 30 分钟，可以搜完所有 10 个点位，获得 10 × 4 = 40 物资，总耗时约 25 分钟。

A 12

20

说明： 从 A 出发，12 分钟极限。最优路线：A → B → C → H → J，搜 5 个点，耗时 2×5（搜索）+ 0.5×4（通行）= 12 分钟。

I 20

32

说明： 从 I 出发，20 分钟。最优路线：I → G → D → B → E → H → C → J，搜 8 个点，耗时 2×8 + 0.5×7 = 19.5 分钟。

数据范围

• 地图固定，如题目描述所示。
• 出生点 $S ∈ (A, B, C, I)$。
• 时间限制 T：$1 ≤ T ≤ 30$。
• 每个点位物资为 4，搜索耗时 2 分钟。
• 每条边通行耗时 0.5 分钟。