CF436A Feed with Candy

The hero of the Cut the Rope game is a little monster named Om Nom. He loves candies. And what a coincidence! He also is the hero of today's problem. One day, Om Nom visited his friend Evan. Evan has $ n $ candies of two types (fruit drops and caramel drops), the $ i $ -th candy hangs at the height of $ h_{i} $ centimeters above the floor of the house, its mass is $ m_{i} $ . Om Nom wants to eat as many candies as possible. At the beginning Om Nom can make at most $ x $ centimeter high jumps. When Om Nom eats a candy of mass $ y $ , he gets stronger and the height of his jump increases by $ y $ centimeters. What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?

The first line contains two integers, $ n $ and $ x $ $ (1

Print a single integer — the maximum number of candies Om Nom can eat.

One of the possible ways to eat $ 4 $ candies is to eat them in the order: $ 1 $ , $ 5 $ , $ 3 $ , $ 2 $ . Let's assume the following scenario: 1. Initially, the height of Om Nom's jump equals $ 3 $ . He can reach candies $ 1 $ and $ 2 $ . Let's assume that he eats candy $ 1 $ . As the mass of this candy equals $ 4 $ , the height of his jump will rise to $ 3+4=7 $ . 2. Now Om Nom can reach candies $ 2 $ and $ 5 $ . Let's assume that he eats candy $ 5 $ . Then the height of his jump will be $ 7+5=12 $ . 3. At this moment, Om Nom can reach two candies, $ 2 $ and $ 3 $ . He won't eat candy $ 2 $ as its type matches the type of the previously eaten candy. Om Nom eats candy $ 3 $ , the height of his jump is $ 12+3=15 $ . 4. Om Nom eats candy $ 2 $ , the height of his jump is $ 15+1=16 $ . He cannot reach candy $ 4 $ .