TR-MO 2014 Problem 6

$5$ airway companies operate in a country consisting of $36$ cities. Between any pair of cities exactly one company operates two way flights. If some air company operates between cities $A, B$ and $B, C$ we say that the triple $A, B, C$ is properly-connected. Determine the largest possible value of $k$ such that no matter how these flights are arranged there are at least $k$ properly-connected triples.