题目描述

有一个取物小游戏，在平面直角坐标系中，每一轮游戏分为随机产生物品和取物品两个环节：

先是随机产生物品：每轮随机在横纵坐标都为整数的 $k$ 个坐标点上产生物品，每件物品有按重量计价的单价和重量；

然后是游戏者取物品：每轮游戏者必须取走当前所有物品中的 $m$ 件物品。设物品价值为 $\verb|v|$ ，重量为 $w$，与坐标原点距离为 $d$，总结经验发现，每次取物品时，优先取走当前所有物品中的 $\dfrac{\verb|v|_i}{w_i \times d_i}$ 值最大的物品（如果有多个满足条件的物品，那么取走重量最小的），游戏者获得的分数最高。

求经过多轮游戏后，在游戏者获得最高得分的情况下，游戏者取走的所有物品的总重量。

输入格式

第一行是三个整数 $n,k,m$，分别表示游戏进行的总轮次数、每轮游戏产生的物品数和每轮游戏取走的物品数；

接下来有 $n$ 组输入，每组输入间有一个空行，第 $i$ 组有 $k$ 行，表示第 $i$ 轮产生的物品信息，每行是 $4$ 个用空格隔开的整数 $x,y,p,w$，分别是一件物品所在位置横坐标、所在位置纵坐标、单价和重量。

输出格式

一个整数，就是经过多轮游戏后，在游戏者获得最高得分的情况下，游戏者取走的所有物品的总重量。

输入输出样例

2 3 2

1 1 1 2
-1 1 2 6
4 4 4 3

1 -1 1 4
-1 -1 1 6
2 -2 18 5

16

说明/提示

对于输入样例，第一轮取走的 $2$ 件物品是：-1 1 2 6 和 1 1 1 2；

第二轮取走的 $2$ 件物品是：2 -2 18 5 和 4 4 4 3 时游戏者获得的分数最高，取走的所有物品的总重量是 $16$。

👀️ 对于 $100\%$ 的数据 $1 \leq n \leq 10000,1 \leq m \leq k \leq 100,-100\leq x,y \leq 100,1 \leq p,w \leq 100$。