题目描述

小爱正在接受忍者训练。在接下来的每一秒里，她的身边都会飞来一只水果。水果将会分左、右及上、下共四个方向接近小爱，如下图所示：

一开始，小爱朝向为右侧，如果她想切来自左侧的水果，就必须转向，每次转向将消耗 6 点体力。如果她想切一个来自上方的水果，需要消耗 3 点体力，而切一个来自下方的水果，只需要消耗 2 点体力。

假设她拥有 m 点体力，请问她最多能切掉多少只水果？

输入格式

第一行：两个整数表示 n 和 m；
第二行：n 个字符 s1s2...sn，表示每一秒钟水果飞来的方向：

1 表示右上方向；

2 表示右下方向；

3 表示左上方向；

4 表示左下方向。

输出格式

单个整数：表示最多可以切掉多少只水果。

数据范围

对于 30% 的数据，1≤n≤10；

对于 60% 的数据，1≤n≤100；

对于 100% 的数据，1≤n≤1000，1≤m≤10⁴。

样例数据

输入:

10 40

1234123412

输出:

8