Maximum Books on a Shelf

You are given a set of books where each book is characterized by a genre (a string) and a weight (an integer). Your task is to determine the maximum number of books that can be placed on a shelf subject to the following constraints:

• The total weight of the selected books does not exceed a given capacity.
• No two consecutive selected books have the same genre.

Note: Books should be considered in an order that favors lighter books first (i.e. sort by weight in ascending order) to potentially maximize the number of books on the shelf.

The formula for the capacity constraint can be written in LaTeX as:

$$ \sum_{i=1}^{k} w_i \leq C $$

where \(w_i\) is the weight of the \(i\)th selected book and \(C\) is the overall capacity.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers \(n\) and \(C\), where \(n\) is the number of books and \(C\) is the weight capacity of the shelf.
2. The following \(n\) lines each contain a string and an integer separated by space, representing the genre of the book and its weight, respectively.

outputFormat

Output a single integer to standard output (stdout), which is the maximum number of books that can be placed on the shelf under the given constraints.

## sample

4 7
fiction 2
mystery 3
fiction 4
non-fiction 1

3