寒枫将军将要带领他的部队去圣雪山消灭那里的冰龙。
部队分成了若干个小队，属于同一个小队的人兵种相同。寒枫将军有着杰出的指挥能力，在战斗的时候，寒枫将军能够让所有相同兵种的人互相配合，使t个相同兵种的人发挥出t2的战斗力；寒枫将军还能让不同兵种的人互相配合，使整个部队的战斗力是所有兵种战斗力的和。
例如，部队中有3个小队，分别是5个人的步兵小队，3个人的步兵小队，3个人的骑兵小队。那么步兵战斗力为64，骑兵战斗力为9，部队总战斗力为73。
寒枫将军需要知道他的部队的战斗力是多少。
3
5 1
3 1
3 2
73
10%的数据，n=1
30%的数据，n≤1000
另有20%的数据，ai=1
另有30%的数据，bi≤1000
100%的数据，1≤n≤100000，1≤ai≤10000，1≤bi≤1,000,000,000
