题目内容

小 A 是一个喜欢玩电子游戏的人。他今天接触到了一款名为 $FS$ 的新游戏，在这个游戏中，有一个无穷大的坐标网格地图，在这个游戏的夜间模式中，玩家需要建造若干照明塔来为地图照明，具体地，小 A 随时可以在 $(a,b)$ 处建造一个光照半径为 $r$ 的照明塔，建造完成后所有满足 $max(丨x-a丨,丨y-b丨) <=r$ 的点 $(x,y)$ 处的光照等级都会加 $1$ (请注意这里是切比雪夫距离小于等于 $r$ 而非欧几里得距离，初始时所有位置的光照等级均为 $0$ )。

小 A 现在希望达成 $FS$ 游戏中的一项成就，叫做“灯火通明”。具体而言，玩家需要使某一空点处(即该坐标处没有照明塔)的光照等级增加到至少 $L$ 。

小 A 可以通过建造多个照明塔来达到这一目的。在当前模式下有 $n$ 种照明塔可供建造，第 $i$ 种照明塔的光照半径为 $r_i$ ，造价为 $v_i$ ，且至多能建造 $a_i$ 座。