Airports

Problem Statement

An airline company offers flights out of n airports, labeled from 1 to n.

The flight time tij from airport i to airport j is known for each ij, although it may not be the case that tij = tji.

Upon landing at a given airport, a plane must be inspected before flying again. Inspection time pi is dependent on the airport where the flight landed, not where previous flight originated.

Given a set of m flights that the airline company must provide, determine minimum number of planes company needs to purchase.

The airline may add unscheduled flights to move the airplanes around if that would reduce total number of planes needed.

Input File

Lines:

Line 1: n (number of airports) m (number of flights to maintain)

Line 2: (inspection times, pi, i = 1..n)

Line 3: j=1 (3-2), all the tij's (tii=0)

...

n+2 : j = n (n+2 - 2), all of the tij's

n+3: <source airport> <destination airport> <flight time>

...

n + 2 + m: ditto