3245 - 王国的福利
题目描述
在一个 N \times M 的矩形王国里，从 1,1 点到 N,M 点的每个整数坐标的位置，都生活着一个居民。
这个王国的国王会不定期的为子民发放福利。经统计，共有 T 次福利发放。每次国王会选择以 X_i,Y_i 为左上角 X_j,Y_j 为右下角的小矩形，为该小矩形中的每位居民发放 C_i 元作为福利。
请问从第一次发放开始已统计，最早在第几次福利发放时，有居民在历次福利发放中，一共领取到了不少于 S 元。
输入
第 1 行输入整数 N,M,T,S。
接下来 T 行，每行有五个整数 X_i,Y_i 和 X_j,Y_j,C_i，含义如题所述。
输出
输出一个整数，代表题目询问的结果。
如果 T 次福利发放结束，始终没有居民一共领取不少 S 元的福利，请输出 -1。
样例
输入
10 10 5 7 2 9 7 10 7 6 5 8 8 1 1 2 10 2 5 5 1 8 9 8 8 7 9 9 8
输出
1
输入
20 20 8 30 9 10 15 11 4 2 1 18 13 3 2 10 14 12 3 5 10 16 11 5 7 5 16 17 3 10 4 13 20 9 10 2 16 17 5 8 4 17 13 2
输出
7
输入
20 20 10 52 4 5 18 12 4 4 1 15 17 2 10 8 17 12 7 10 1 14 18 5 10 7 12 13 5 7 1 14 17 1 4 2 10 15 5 4 3 20 12 9 8 10 18 12 5 1 2 13 17 8
输出
-1
说明
数据范围
对于 50\% 的数据 3 \le N,M \le 100，1 \le T \le 100。
对于 100\% 的数据 3 \le N,M \le 200，1 \le T \le 10^5，X_i \le X_j，Y_i \le Y_j，1 \le C_i \le 10^4，1 \le S \le 10^9。
标签
