Zorg

Time limit: 3.5s Memory limit: 64MB Input: Output:

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 QQ danger positions in the matrix, where if you enter, Suzi's people have recognized you and are on your trail. They take TT time to catch you. But there are SS 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)(1,1,1) to (N,M,K)(N,M,K).
You can move in all 66 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,TN,M,K,Q,S,T and GG, 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 NN rectangles of the shape MKM \cdot K, representing each 2D zone in the realm, each square of the shape (i,j,k)(i,j,k) being one of the NMKN \cdot M \cdot K, and here we will read the maximum amount in each zone.
Then NN more rectangles of the shape MKM \cdot K will follow, representing each 2D zone in the realm, each square of the shape (i,j,k)(i,j,k) being one of the NMKN \cdot M \cdot K zones, and here we read the time to travel to a respective zone.
On the next QQ lines will be 33 natural numbers: x,yx,y and zz, these are the coordinates of the danger positions.
On the next SS lines will be 33 natural numbers: x,yx,y and zz, 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

  • 1N,M,K501 \leq N,M,K \leq 50
  • 0Q300 \leq Q \leq 30
  • 0S300 \leq S \leq 30
  • 0G1090 \leq G \leq 10^9
  • 1T1091 \leq T \leq 10^9
  • 0travel time1090 \leq travel \ time \leq 10^9
  • To avoid confusion, the start time at position (1,1,1)(1,1,1) is 00, so in each test, the index pass time (1,1,1)(1,1,1) will be 00.
  • If there is no solution, 1 1-1 \ -1 will be displayed
  • For displaying the correct maximum of armament, 20%20 \% of the score will be awarded, respectively 80%80 \% of the score for the minimum time Costel has to spend in the realm.
# Points Constraints
1 20 N=1N=1, Q=0Q = 0, S=0S = 0, armament in all areas of the realm is GG
2 20 Q=0Q = 0, S=0S = 0, armament in all areas of the realm is GG
3 60 No additional constraints

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)(1,2,1)(1,2,2)(2,2,2)(2,2,3)(2,3,3)(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 1414, and the maximum weapon Costel can own is 55.

Log in or sign up to be able to send submissions!