Find $a_i, b_i$ such that they are all distinct Very tough, I spent at least an hour, not solving this!

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$.

So each element can only be used once. 
$k_1 = \{1, 2 \}$ and $k_2 = \{3, 4  \}$
The maximum difference possible set is $A = \{1, 2008 \}$. $2008$ can be used once, $2007$ once [ 1, 2007], $2006$ once [1, 2006].
But it gets very confusing?
HINTS please?
 A: PARTIAL SOLUTION (UPPER BOUND)
As sketched out in some of the comments, a critical step in the problem is establishing a good upper bound.  It isn't terribly hard to come up with good candidates...hard to see how to show that one of them is actually maximal.
So.  Take a maximal list, say it has $k$ elements.  Sum up all the elements that appear in your list, let $\mathscr S$ denote that sum.  As all the elements are distinct, we must have $$\mathscr S\;≥\;1+2+3\;+\;...+\;2k\;=\;k(2k+1)$$
Now, recompute the sum by adding them up pair by pair.  As all the pair sums are distinct and bounded above by $2009$ we must have:
$$\mathscr S \;≤\;2009+2008\;+\;...\;+\;2009-(k-1)\;=\;2009k-\frac {k(k-1)}{2}\;=\;\frac {k(4019-k)}{2}$$
Combining these two inequalities we see that $$\frac {k(4019-k)}{2}≥k(2k+1)$$
Divide by $k$ and rearrange terms to get $$4017≥5k$$ from which we see at once that $$k≤803$$
(Note:  we used the fact that $k$ must be an integer).
Now all you need to do is to construct a list with $803$ elements.  Note:  this is not as hard as it sounds.  Hint:  try to use as many small integers as you possibly can.
A: You already gave hints yourself :-)
2009 cannot be in a pair, because already {2009, 1} leads to a sum that is larger than 2009. The remaining 2008 elements of the set can be in a pair.
Each element can only be used once. Since there are two elements in each pair, the number of pairs cannot be larger than the number of usable elements in the set divided by two:
$k \leq \frac{2008}{2}$.
How many unique pairs can you form if you go $k_1=\{1,2008\}, k_2=\{2,2007\}, \dots$?
