最近小仓鼠发现了一款另类塔防游戏^O^，该游戏的地图是一个n*m网格，现在左上角单元格位于(1,1)，而右下角单元格位于(n,m)。

现在有一大批敌军站在(1,1)单元格内，他们的目标是达到位于(n,m)的水晶。敌军每次只能移动到当前相邻的四个格子中，即当他们在(x,y)单元时，他们只能移动到(x-1,y)，(x+1,y)，(x,y-1)或(x,y+1)四个单元格且不能超出地图。
现在一些格点上方有大石块，每个石块都是矩形的，第i个石块位于xl_i,yl_i 和xr_i,yr_i 之间小仓鼠可以选择花费w_i点魔力击落石块，使得敌军无法到达石块覆盖的格点上。现在小仓鼠要阻止敌军到达水晶。请输出小仓鼠可以阻止敌军到达水晶至少要花费的魔力，或者输出-1表示无论如何都不能阻止敌军到达水晶。

本题输入含多组数据。第一行有一个数字T (1≤T≤10)，表示数据总数。

对于每组数据，第一行有三个整数n,m,k(2≤n,m≤10⁹,1≤k≤2000)，表示地图的大小和石块的数量。
接下来的k行，每行包含5个整数xl_i,xr_i,yl_i,yr_i,w_i(1≤xl_i≤xr_i≤n,1≤yl_i≤yr_i≤m,1≤w_i≤10⁹)，表示石块的覆盖范围和击落花费。保证无石块覆盖(1,1)或(n,m)。