Push Z150 to the Quiet Western Front

Probability

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.