진흙 흐름

로스앤젤레스처럼 언덕이 많은 지역에서는 허리케인 같은 폭우가 진흙 산사태를 일으킨다. 비는 흙과 잔해를 느슨하게 만들고, 느슨해진 것들은 비탈을 따라 흘러내린다. 아래쪽에서는 그곳에 내리는 비와 위에서 내려온 물이 흙을 더 느슨하게 만들어, 곧 큰 진흙 산사태가 쏟아져 내려온다. 진흙은 집과 도로를 묻고 진로에 있던 사람들을 숨지게 하기도 한다. 이 문제에서는 처음의 흙 분포와 각 칸에 내리는 비가 주어졌을 때, 최종적으로 어느 한 칸에 쌓이는 흙의 최대량을 구한다.

지역은 직사각형 격자이다. 각 칸에는 높이, 처음 놓인 흙의 양, 그 칸에 내리는 비의 양, 그리고 그 칸의 흙을 떨어뜨리는 데 필요한 물의 임계값이 있다. 흙과 비는 높이를 바꾸지 않는다.

칸에 도착한 물은 상하좌우로 인접한 칸 중 엄격하게 더 낮은 칸으로 흘러내린다. 더 낮은 인접 칸이 여러 개면 물은 그 칸들에 고르게 나뉜다. 더 낮은 인접 칸이 없으면 물은 그 칸에 머문다. 칸에 도착한 물의 양이 임계값을 엄격하게 넘으면, 그 칸의 흙이 모두 흘러내리기 시작한다. 물은 지나가는 모든 칸에 대해 계산한다. 흙이 떨어지면 엄격하게 더 낮은 인접 칸들에 고르게 나뉜다. 떨어진 흙은 더 내려갈 수 없을 때까지 계속 움직이며, 지나가는 칸의 물이 새 흙을 떨어뜨리기에 부족하더라도 멈추지 않는다. 흙은 다른 흙을 떨어뜨리지 못하고, 물만 흙을 떨어뜨릴 수 있다.

지역은 높은 산으로 둘러싸여 있어서 물과 진흙이 경계 밖으로 나가지 않는다. 지도의 어느 한 칸에 최종적으로 쌓이는 흙의 최대량을 구한다. 모든 계산에는 float가 아니라 double을 써야 한다.

1 일반적으로 어떤 프로그래밍 대회에서든, 실제 프로그래밍에서든 double을 쓰지 않을 이유는 없다. 아끼는 메모리는 그만한 가치가 없다. 많은 프로그래머가 float를 "f-word"로 여긴다.

첫 줄에는 데이터 세트의 개수 K (1 ≤ K ≤ 100)가 주어진다. 각 데이터 세트는 지역의 크기 n과 m (1 ≤ n, m ≤ 300)을 나타내는 두 정수로 시작한다. 이어서 각각 n줄, m열의 실수로 이루어진 블록 네 개가 주어진다. 블록의 y행 x열 값은 칸 (x, y)에 해당한다.

• 높이: $0.0 \le h_{y,x} \le 100.0$
• 흙: $0.0 \le s_{y,x} \le 100.0$
• 비: $0.0 \le r_{y,x} \le 100.0$
• 임계값: $0.0 \le t_{y,x} \le 100.0$

실수 비교는 같거나 적어도 0.0001 차이가 나도록 되어 있어서 반올림 문제는 생기지 않는다.

각 데이터 세트마다 "Data Set x:"를 한 줄에 출력한다. x는 데이터 세트 번호이다. 그다음 어느 한 칸에 최종적으로 쌓이는 흙의 최대량을 출력한다. 데이터 세트마다 출력 뒤에 빈 줄을 하나 둔다.