#P18340. Sweet Sugar IV

Sweet Sugar IV

Sweet Sugar IV

标准输入,标准输出。

为了庆祝即将到来的儿童节,将举办一场收集糖果的游戏。游戏地图是一个 nn 行 mm 列的网格,行编号为 11 到 nn,列编号为 11 到 mm。

地图中有 dd 块糖。第 ii 块糖位于格子 (xi,yi)(x_i,y_i),甜度为 sis_i。每个格子至多有一块糖。

有 kk 个棋子,它们最初全部位于同一个格子 (Sx,Sy)(S_x,S_y)。每次操作,你可以选择一个棋子,将它从 (x,y)(x,y) 移到 (x+1,y)(x+1,y) 或 (x,y+1)(x,y+1);棋子不能移出地图。一个格子可以同时容纳多个棋子。

只要某个棋子位于一个有糖的格子上,你就会取得这块糖。每块糖只能被取得一次。特别地,如果起点有糖,它会立即被取得一次。

你可以进行任意多次合法操作,也可以随时停止。最终得分为取得的所有糖的甜度之和。

地图中还有 pp 个矩形障碍。一个障碍用 [x1,x2]×[y1,y2][x_1,x_2]\times[y_1,y_2] 表示,其中的所有格子都是危险格。棋子不能进入任何危险格。障碍满足以下保证:

  • 地图边缘不会出现危险格,即 2≤x1≤x2≤n−12\le x_1\le x_2\le n-1,2≤y1≤y2≤m−12\le y_1\le y_2\le m-1。
  • 任意两个不同的障碍既不重叠,也不接触。这里的“接触”包括角接触:若两格满足 max⁡(∣x−x′∣,∣y−y′∣)≤1\max(|x-x'|,|y-y'|)\le1,则它们视为相邻;相邻的两个危险格必须属于同一个障碍。

你会独立重玩这个游戏 qq 次。每次重玩可以使用不同的起点 (Sx,Sy)(S_x,S_y) 和棋子数 kk;所有糖都会恢复。给定地图、糖和每次重玩的参数,请分别求出能够得到的最大得分。

输入格式

第一行包含五个整数 n,m,p,d,qn,m,p,d,q,依次表示行数、列数、障碍数、糖的数量和重玩次数。

接下来 pp 行,每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示一个闭矩形障碍。它覆盖的行号为 x1x_1 到 x2x_2,列号为 y1y_1 到 y2y_2。

接下来 dd 行,每行包含三个整数 xi,yi,six_i,y_i,s_i,表示一块糖的位置和甜度。糖的位置互不相同,且都是安全格。

接下来 qq 行,每行包含三个整数 Sx,Sy,kS_x,S_y,k,表示一次独立重玩的起点和棋子数。起点保证安全。

输出格式

输出 qq 行,第 ii 行包含一个整数,表示第 ii 次重玩的最大得分。

数据范围

  • 1≤n,m≤1051\le n,m\le10^5,nm≤106nm\le10^6;
  • 0≤p≤1050\le p\le10^5;
  • 1≤d≤2⋅1051\le d\le2\cdot10^5,1≤q≤3⋅1051\le q\le3\cdot10^5;
  • 每个障碍满足 2≤x1≤x2≤n−12\le x_1\le x_2\le n-1,2≤y1≤y2≤m−12\le y_1\le y_2\le m-1,不同障碍不重叠且不八方向接触;
  • 1≤xi≤n1\le x_i\le n,1≤yi≤m1\le y_i\le m,1≤si≤1091\le s_i\le10^9;
  • 1≤Sx≤n1\le S_x\le n,1≤Sy≤m1\le S_y\le m,1≤k≤51\le k\le5。

输入只有一组地图;其中包含 qq 次独立询问。

样例输入 1

3 3 1 4 5
2 2 2 2
1 1 1
3 3 1
1 2 3
2 1 5
1 1 1
1 1 2
1 3 2
1 2 2
2 1 1

样例输出 1

7
10
1
4
6

样例输入 2

5 7 1 3 4
2 3 3 4
3 1 1
2 2 10
5 4 100
1 2 1
1 2 2
1 1 2
2 7 1

样例输出 2

110
110
111
0

样例说明

第一组样例中,从 (1,1)(1,1) 出发只用一个棋子,可以沿左侧绕过障碍,取得甜度为 1,5,11,5,1 的三块糖,得分为 77。使用两个棋子时,可以分别沿障碍两侧移动,取得全部四块糖,总分为 1010。

第二组样例的最后一次重玩从 (2,7)(2,7) 出发。棋子只能向下或向右移动,因此一块糖也取不到,答案为 00。