LCC '22 Contest 4 S1 - Pens

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

Emilio wants to write a story! He has N pens, each with colour c_i and n_i millilitres of ink, and an infinite supply of paper. He wants to write a story with a particular colour. He has calculated the number of pages that he wishes to write, and thus has calculated that he needs M millilitres of ink. To write the story, he may only use one colour, though he is allowed to use multiple pens of the same colour. Your task is to find the number of different colours that he could write the story with.


1\le N\le 10^5

1\le c_i\le 10^6

1\le n_i \le 10^4

1\le M\le 10^9

Input Specification

The first line contains two integers, N and M, respectively

The next N lines each contain two integers, c_i and n_i, respectively.

Sample Output

One integer, the number of colours that he could write his story with.

Sample Input

5 6
4 7
3 2
4 2
3 3
1 8

Sample Output


Sample Explanation

He has a total of 7+2=9 millilitres of colour 4, 2+3=5 millilitres of colour 3, and 8 millilitres of colour 1. Two of these colours have a total volume of over 6, so there are 2 colours he could write with.


There are no comments at the moment.