新年将近，犇爸打算从神犇的愿望单中选择一些来作为神犇的新年礼物。愿望单上列出了n种礼物，第i种礼物价格为c_i。他准备了m元钱来买礼物，并且期望神犇收到礼物时震惊度最高。

神犇收到礼物时震惊程度和其价格相同；但如果同一件礼物收到第二次则震惊度为礼物价格的2倍，第三次收到时震惊度为礼物价格的4倍，即每次收到同一礼物震惊度都是上一次的两倍。

第一行，有单个空格分隔的2个整数m,n，分别表示犇爸准备的钱数和愿望单上的礼物数。

接下来n行，每行2个整数w_i,x_i分别表示该礼物的价格和个数。

对于100%的数据：

1\le m \le 3000;

1\le n \le 10；

1\le w_i \le 1000；

1\le x_i \le 40。

一行，一个整数，表示神犇能达到的最大震惊值。