2415: 苹果旅游

xiaoT发现山谷相当的大，准确地说应该是相当的长，xiaoT想到山谷的那头去看看，但是靠xiaoT走路的速度，到那边要n年。还好xiaoT可以买一些苹果，它把这些苹果当成动力，根据火箭发射的原理，如果xiaoT把苹果向后扔，xiaoT就会向前进。

苹果有两种，一种青苹果，一种红苹果。

已知到山谷的长度为k，用一些（同一种类）苹果可以通过的路程为1。

苹果的价格是不一样的，红苹果的价格是红苹果个数的四次方。

青苹果的价格就是青苹果个数。

第一行有一个正整数n表示xiaoT走路到那边需要的时间。

第二行有一个正整数k表示山谷的长度。

接下来k行，每行两个正整数，分别表示通过该段：

如果使用红苹果，则需要的数量为a

如果使用青苹果，则需要的数量为b

2296
3
3 1000
2 5000
4 8000

2296