Optimal Flight Maneuver Planning

The supersonic fighter plane Huaxia 60 is capable of performing three basic maneuvers. In combat the key is to change the flight altitude and speed as quickly as possible. The three maneuvers are:

• Constant‐speed Climb: Fly at constant speed while climbing, increasing altitude by Δh feet. The flight state changes from (H, V) to (H+Δh, V). The time cost depends on the current altitude and speed and is provided by Table 1.
• Horizontal Acceleration: Accelerate horizontally, increasing the speed by 1 Mach (while altitude remains the same). The flight state changes from (H, V) to (H, V+1). Its time cost is given in Table 2.
• Vertical Dive: Dive vertically and decrease altitude by Δh feet while accelerating 1 Mach. The flight state changes from (H, V) to (H-Δh, V+1). The time cost is given in Table 3.

Some conditions are imposed:

• The speed V is always an integer Mach number between 1 and 6 (inclusive).
• The altitude H is always a multiple of Δh feet. In this problem, Δh = 15000 feet and the allowable altitudes are 0, 15000, 30000, 45000, 60000, and 75000.
• A maneuver can only be performed if, after its execution, the altitude and speed remain within the permissible range.

The time cost tables (which depend on the current altitude and speed at the start of the maneuver) are hard‐coded as follows (here, the altitude index is defined by H_index = H/15000):

Table 1 (Constant‐speed Climb – T1)

Altitude Index	V=1	V=2	V=3	V=4	V=5	V=6
0 (H=0)	12	11	10	9	8	7
1 (H=15000)	8	8	7	7	7	7
2 (H=30000)	7	7	7	7	7	7
3 (H=45000)	7	7	7	7	7	6
4 (H=60000)	7	7	7	7	7	7
5 (H=75000)	-	-	-	-	-	-

Table 2 (Horizontal Acceleration – T2)

For any altitude row 0 through 5 and for V from 1 to 5:

• For altitude index 0: cost = 6 seconds.
• For altitude indices 1 to 5: cost = 5 seconds.

Table 3 (Vertical Dive – T3)

This maneuver is only available when altitude index > 0 (i.e. H > 0) and for V from 1 to 5.

• For altitude indices 1 to 4: cost = 7 seconds (for any V).
• For altitude index 5 (H = 75000): cost = 7 seconds for V = 1,2,3, and 6 seconds for V = 4,5.

Given an initial flight state (H1, V1) and a target state (H2, V2), your task is to compute the minimum time needed to reach the target state by performing a sequence of valid maneuvers.

Note: If the initial state is the same as the target state, the minimum time is 0. In the sample case below, changing from H = 0 ft, V = 1 Mach to H = 75000 ft, V = 6 Mach can be done in 79 seconds.

inputFormat

The input consists of four space‐separated integers: H1 V1 H2 V2

• H1 and H2 are altitudes (in feet) and are multiples of 15000, with 0 ≤ H1, H2 ≤ 75000.
• V1 and V2 are speeds in Mach and are integers between 1 and 6 (inclusive).

outputFormat

Output a single integer representing the minimum time (in seconds) to change from the initial state (H1, V1) to the target state (H2, V2) using the allowed maneuvers.

sample

0 1 75000 6

79