Maximum Requests Under Threshold

You are given N servers. Each server has a maximum request capacity R_i and an average response time A_i in milliseconds. Your task is to select a subset of these servers so that the overall average response time does not exceed a given threshold T.

More formally, if you select k servers with response times \(A_1, A_2, \dots, A_k\), the condition to satisfy is:

\(\frac{A_1 + A_2 + \cdots + A_k}{k} \le T\)

Your objective is to maximize the total request capacity \(\sum_{i=1}^{k}R_i\) while meeting the response time constraint. Note that a server with response time greater than T cannot be used.

inputFormat

The first line contains two integers N and T, where N is the number of servers and T is the threshold average response time (in milliseconds). This is followed by N lines, each containing two integers R_i and A_i where R_i is the maximum requests per second the i-th server can handle and A_i is its average response time.

outputFormat

Output a single integer representing the maximum total number of requests per second that can be handled by selecting a subset of servers such that the average response time of the selected servers does not exceed T.

3 300
500 200
300 100
400 500

800