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?**