Push Z150 to the Quiet Western Front

Discrete Mathematics Level 2

If we pick 77 numbers randomly from the set \(\{1,2,3,4,...,150\}\), we are guaranteed to have at least \(k\) pairs of numbers where the difference between each pair is 19. What is the maximum possible value of \(k?\)

Please treat a pair as a combination, not a permutation.