FiFo | RoAlgo Educational Contest #1 | Zorg

Task

You're in the realm of Zorg, a very special realm with a three-dimensional dimension. Zorg was attacked by Suzi, so Zorg lost his throne and was sent to the slammer.
Zorg asks Costel for help to put him back on the throne, but Suzi is very careful. She has placed in each area of the realm a maximum weight of armaments you can enter, or you will be discovered and Zorg will be executed. We want to have as much armaments as possible so that we can dethrone Suzi, but each area of the realm has a specific time to enter it. There are $Q$ danger positions in the matrix, where if you enter, Suzi's people have recognized you and are on your trail. They take $T$ time to catch you. But there are $S$ safe positions in the matrix, where if you enter them, Suzi's men will lose track of you, and you can continue on your way to Suzi. On the way to a safe position, the weapons limitation will be ignored, because Suzi's men know you're there.
Find the highest amount of armaments Costel can carry, then the shortest time to get from $(1,1,1)$ to $(N,M,K)$.
You can move in all $6$ directions, (NORTH, SOUTH, EAST and WEST) on the 2D plane, and up or down if you want to change the level in the matrix.

Input data

On the first line are five integers, $N,M,K,Q,S,T$ and $G$, representing the dimensions of the realm of Zorg, the number of danger positions, the number of safe positions, the time limit for Suzi's men to catch you if you have entered a danger position, and the maximum number of weapons possible in the realm.
Next will follow $N$ rectangles of the shape $M \cdot K$, representing each 2D zone in the realm, each square of the shape $(i,j,k)$ being one of the $N \cdot M \cdot K$, and here we will read the maximum amount in each zone.
Then $N$ more rectangles of the shape $M \cdot K$ will follow, representing each 2D zone in the realm, each square of the shape $(i,j,k)$ being one of the $N \cdot M \cdot K$ zones, and here we read the time to travel to a respective zone.
On the next $Q$ lines will be $3$ natural numbers: $x,y$ and $z$, these are the coordinates of the danger positions.
On the next $S$ lines will be $3$ natural numbers: $x,y$ and $z$, these are the coordinates of the safe positions.

Output data

It will display the maximum number of weapons and the minimum time spent traveled by Costel towards Suzi.

Constraints and clarifications

• $1 \leq N,M,K \leq 50$
• $0 \leq Q \leq 30$
• $0 \leq S \leq 30$
• $0 \leq G \leq 10^9$
• $1 \leq T \leq 10^9$
• $0 \leq travel \ time \leq 10^9$
• To avoid confusion, the start time at position $(1,1,1)$ is $0$, so in each test, the index pass time $(1,1,1)$ will be $0$.
• If there is no solution, $-1 \ -1$ will be displayed
• For displaying the correct maximum of armament, $20 \%$ of the score will be awarded, respectively $80 \%$ of the score for the minimum time Costel has to spend in the realm.

Comment

Due to the very large input data, we recommend using the following lines at the beginning of the main() function in the C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

2 3 3 1 1 5 13
5 3 4
8 5 9
2 3 8
9 1 3
10 13 8
2 2 5
0 1 3
2 5 9
8 2 3
5 8 8
8 2 2
1 9 3
1 2 2
2 2 2

stdout

5 14

Explanation

Route: $(1,1,1) \rightarrow (1,2,1) \rightarrow (1,2,2) \rightarrow (2,2,2) \rightarrow (2,2,3) \rightarrow (2,3,3)$. The time spent through the realm is $14$, and the maximum weapon Costel can own is $5$.