1963 - 最小和

Input

输入共一行,10个正整数,依次为 C,N,xzero,xprod,xadd,xmod,yzero,yprod,yadd,ymod。

Output

输出共一行,为所求的最小值。

Examples

Input

4 10 0 1 1 456 1 1 1 456 

Output

5 

Hint

对于全部的数据,1<=C<=16,1<=N<=10000,1<=xmod,ymod<=1000000000, 0<=xzero,xprod,xadd

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