T467231 打蚊子

你来到了一个夏令营，但是这里的蚊子实在太多了，为了让~~自己睡好觉~~蚊子安息，你决定开始打蚊子。

你的墙上有$n×n$个格子，每个格子里要么只有$1$只蚊子，要么没有蚊子，你有$m$种工具，第$i$种工具一次可以消灭$a[i]*a[i]$范围的蚊子，价格是$w[i]$元。 求要消灭所有蚊子要花多少钱？

第一行两个正整数，分别是$n$和$m$ 接下来$n$行，每行$n$个数字，$0$代表没有蚊子，$1$代表有蚊子 接下来$m$行，每行两个数，共$m$行，分别是$a[i]$和$w[i]$

一个正整数，表示要花的钱。

$1≤n,m≤5000$ $1≤a[i],w[i]≤1000$