Farmer John is bringing his N cows, conveniently numbered 1 \ldots N, to the county fair, to compete in the annual bovine talent show! His ith cow has a weight w_i and talent level t_i, both integers.

Upon arrival, Farmer John is quite surprised by the new rules for this year's talent show:

(i) A group of cows of total weight at least W must be entered into the show (in order to ensure strong teams of cows are competing, not just strong individuals), and

(ii) The group with the largest ratio of total talent to total weight shall win.

FJ observes that all of his cows together have weight at least W, so he should be able to enter a team satisfying (i). Help him determine the optimal ratio of talent to weight he can achieve for any such team.

Problem credits: Brian Dean

#4074 upload 2 done 1 how_to_reg 1

Talent Show timer 2s memory 512MB

#4074

Talent Show 2s 512MB