于神之怒加强版

时间限制:80s      空间限制:512MB

题目描述

给下N,M,K.求


输入格式

输入有多组数据,输入数据的第一行两个正整数T,K,代表有T组数据,K的意义如上所示,下面第二行到第T+1行,每行为两个正整数N,M,其意义如上式所示。


输出格式

如题


样例输入

1 2
3 3 

样例输出

20

提示

1<=N,M,K<=5000000,1<=T<=2000

题解:JudgeOnline/upload/201603/4407.rar


题目来源

命题人:成都七中张耀楠,鸣谢excited上传。