2009 AIME II Problem 12

From the set of integers \{1,2,3,\ldots ,2009\}, choose k pairs \{a_i,b_i\} with a_i<b_i so that no two pairs have a common element. Suppose that all the sums a_i+b_i are distinct and less than or equal to 2009. Find the maximum possible value of k.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.