Background

@kunkka 帮忙出出数据，我写标程

土拨鼠 哈利 想成为一名老六，来坑 波特 大佬。

Description

刚开始，哈利只不过是一个非常弱的(老)n，但它可以通过"jia x"，"jian x"，"cheng x"，"chu x"，(x的值不固定) 四种类型的操作来让自己变强，最终变成(老)6。共有m个可以执行的操作，每个操作可以执行无数次。但，如果操作后哈利的n小于0 或者 操作后哈利的n大于$10^6$ 那出题人就会暴怒，所以不能操作。请你算一算，哈利从n变成6，至少需要多少次操作。如果哈利不能从n变成6，请输出"HL CAN'T BE A LAOLIU"。

Format

Input

第一行两个整数，n，m 后面m行，每行一个可以执行的操作

Output

一个整数，哈利从n变成6最少要执行多少次操作。

Samples

13 5
jian 1
chu 2
cheng 6
chu 13
jian 7

1

7 1
jia 1

HL CAN'T BE A LAOLIU

Limitation

• 样例1解释 ：13 - 7 = 6
• 还有两种办法，但都是两步
• $0≤n≤10^6,1≤m≤100,1≤x≤1000$
• 除法必须整除