#CW59. 左右采撷(harvest)

左右采撷(harvest)

题目描述

花园中有 nn 行、mm 列花朵。第 ii 行第 jj 列的花记作 (i,j)(i,j),它含有 fi,jf_{i,j} 单位花粉。另有 kk 只蜜蜂,第 ii 只蜜蜂的初始位置为 (xi,yi)(x_i,y_i)。所有蜜蜂使用同一个非负整数体力值 pp,但每只蜜蜂可以独立选择一种采集方式:

  • 左右采撷:只在第 xix_i 行采集,并且采集列号 jj 满足 ∣j−yi∣≤p|j-y_i|\le p 的花;
  • 上下采撷:只在第 yiy_i 列采集,并且采集行号 rr 满足 ∣r−xi∣≤p|r-x_i|\le p 的花。

每只蜜蜂只能选择其中一种方式,不能先横向采集再纵向采集,也不能把一次选择拆成多个区间。区间超出花园边界的部分直接忽略。

不同蜜蜂的采集范围可能重叠,但每朵花最多只能计入一次总花粉。也就是说,应先取所有被至少一只蜜蜂覆盖的花朵的并集,再把这些花的花粉量相加。

请问要使所有蜜蜂合计采集到至少 ww 单位花粉,体力值 pp 至少是多少。如果即使把每只蜜蜂的范围扩展到整个对应行或列,也无法收集到 ww 单位花粉,则不存在合法的 pp。

输入格式

从 harvest.in 文件读入数据。

第一行输入 n,m,k,wn,m,k,w。接下来 nn 行每行输入 mm 个正整数 fi,jf_{i,j}。接下来 kk 行每行输入 xi,yix_i,y_i。

输出格式

将结果输出到 harvest.out 文件。

输出满足条件的最小整数 pp,无解时输出 Impossible。

样例 1 输入

3 4 2 20
1 2 3 4
5 6 7 8
9 10 11 12
2 2
3 4

样例 1 输出

1

样例 1 解释

p=0p=0 时,第一只蜜蜂最多采集 66 单位,第二只蜜蜂最多采集 1212 单位,合计 18<2018<20;p=1p=1 时,第一只蜜蜂可横向覆盖第 22 行的第 1∼31\sim 3 列(5+6+7=185+6+7=18),第二只蜜蜂可纵向覆盖第 44 列的第 2∼32\sim 3 行(8+12=208+12=20),并集花粉量不少于 2020。

样例 2 输入

2 3 1 100
1 2 3
4 5 6
1 1

样例 2 输出

Impossible

数据范围

对于全部数据,满足 1≤n,m≤10001\le n,m\le 1000,1≤k≤61\le k\le 6,1≤fi,j,w≤1091\le f_{i,j},w\le 10^9,1≤xi≤n1\le x_i\le n,1≤yi≤m1\le y_i\le m。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼21\sim 2 n,m≤10n,m\le 10,k=1k=1
2 3∼43\sim 4 n,m≤20n,m\le 20,k≤3k\le 3
3 20 5∼85\sim 8 n,m≤200n,m\le 200,k≤3k\le 3
4 9∼129\sim 12 n,m≤200n,m\le 200
5 15 13∼1513\sim 15 所有 fi,j=1f_{i,j}=1
6 25 16∼2016\sim 20 无特殊限制