1583 - [Usaco2009 Mar]Moon Mooing 哞哞叫

Input

第一行两个数，C和N 第二行3个数，a1,b1,c1 第三行3个数，a2,b2,c2

Output

一个整数代表最长的那一次嚎叫

Examples

Input

3 10
4 3 3
17 8 2

Output

65
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题