Puzzle of the Week #559 - Minimal Combinations

I have 2k items and I select k of them. There are N possible combinations that I could have selected. N is a multiple of 1000. What is the smallest k could be?