U130967 冰红茶(tea)

Sophie被姑姑派去买冰红茶，小卖部供应 $m$ 种冰红茶，若同种冰红茶购买多瓶会遭到黑心老板的加价，具体地：第 $i$ 种冰红茶买 $x$ 瓶需要 $a[i]\times x^{b[i]}$ 块钱。每种冰红茶都可以认为是无限供应的。 Sophie现在想总共买 $n$ 瓶冰红茶，请求出她的最小花费。

无

无

样例1的解释： 一共需要买10瓶冰红茶，有一种方案是，第一种买9瓶，总价格是 $2\times 9^1=18$ 元。第二种买1瓶，总价格是 $1\times1^2$ 元。总花费19元。可以证明，没有更少花费的方案。 【数据范围】 对于100%的数据，$1\le a[i]\le 1000, 1\le b[i]\le 4, 1\le n\le 1000, 1\le m\le 5000$ 对于测试点1-3，$n\le 10, m\le 5$ 对于测试点4-6，$n\le 100, m\le 100$ 对于测试点7-8，$n\le 1000, m\le 5000$ 对于测试点9-10，$1\le n\le 1000, 1\le m\le 10^6$