Ciel and Eggs

Chef Ciel has N strange eggs. The i-th egg is broken by tapping exactly Ai times. Ciel needs to break K eggs as soon as possible for cooking a rice omelet. However she has been put in an uncomfortable situation. Someone shuffled the eggs! Ciel knows the values Ai, however she doesn't know which egg is which. She'd like to minimize the worst-case number of taps. What is the minimal number? Input