P2570 [ZJOI2010] 贪吃的老鼠

奶酪店里最近出现了 $m$ 只老鼠！它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产 $n$ 块奶酪，其中第 $i$ 块的大小为 $p_i$，会在第 $r_i$ 秒被生产出来，并且必须在第 $d_i$ 秒之前将它吃掉。第 $j$ 只老鼠吃奶酪的速度为 $s_j$，因此如果它单独吃完第 $i$ 块奶酪所需的时间为 $p_i/s_j$。老鼠们吃奶酪的习惯很独特，具体来说： 1. 在任一时刻，一只老鼠最多可以吃一块奶酪； 2. 在任一时刻，一块奶酪最多被一只老鼠吃。 由于奶酪的保质期常常很短，为了将它们全部吃掉，老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长 $T$ 秒是指所有的奶酪的 $d_i$ 变成 $d_i+T$。同时，使用魔法的代价很高，因此老鼠们希望找到最小的 $T$ 使得可以吃掉所有的奶酪。

无

无

### 样例说明 第一组数据中： 第 $0$ 到第 $1$ 秒： 第一只老鼠吃第一块奶酪； 第 $1$ 到第 $3.5$ 秒： - 第一只老鼠吃第二块奶酪； - 第二只老鼠吃第一块奶酪； 第 $3.5$ 到第 $4.5$ 秒：第一只老鼠吃第一块奶酪。 ### 数据规模 $30\%$ 的数据中，$1 \le n,m \le 5$； $100\%$ 的数据中，$1 \le K \le 5$，$1 \le n,m \le 30$，$1 \le p_i \le 10^5$，$0 \le r_i