A - Product Quality Evaluation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は工場の品質管理を担当しています。この工場では N 種類の商品を製造しており、それぞれ 1 から N までの番号が付けられています。

各商品には「品質指数」と「製造数」という 2 つの指標があります。商品 i の品質指数は A_i、1 日あたりの製造数は B_i 個です。品質指数は値が大きいほど不良品が発生しやすいことを表します。

高橋君は、各商品について「リスクスコア」を計算することにしました。商品 i のリスクスコアは、品質指数 A_i と製造数 B_i の積、すなわち A_i \times B_i で定義されます。リスクスコアが高い商品ほど、注意が必要であることを意味します。

高橋君は、リスクスコアが K 以上である商品を重点的に改善する必要があると考えています。リスクスコアが K 以上の商品の数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq A_i \leq 100 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、商品の種類数を表す整数 N と、リスクスコアの基準値を表す整数 K が、スペース区切りで与えられる。
  • 2 行目から N+1 行目では、各商品の情報が与えられる。
  • i+1 行目 (1 \leq i \leq N) では、商品 i の品質指数 A_i と製造数 B_i が、スペース区切りで与えられる。

出力

リスクスコアが K 以上である商品の数を 1 行で出力せよ。

入力例 1

3 100
10 5
20 10
5 30

出力例 1

2

入力例 2

5 500
15 40
8 100
50 20
30 15
25 25

出力例 2

4

Score : 200 pts

Problem Statement

Takahashi is in charge of quality control at a factory. This factory manufactures N types of products, each numbered from 1 to N.

Each product has two metrics: a "quality index" and a "production quantity." The quality index of product i is A_i, and its daily production quantity is B_i units. A higher quality index indicates that defective items are more likely to occur.

Takahashi decided to calculate a "risk score" for each product. The risk score of product i is defined as the product of the quality index A_i and the production quantity B_i, namely A_i \times B_i. A higher risk score means that more attention is required for that product.

Takahashi believes that products with a risk score of K or higher need to be prioritized for improvement. Find the number of products whose risk score is K or higher.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq A_i \leq 100 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers.

Input

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of product types and an integer K representing the risk score threshold, separated by a space.
  • From the 2nd line to the (N+1)-th line, information about each product is given.
  • The (i+1)-th line (1 \leq i \leq N) contains the quality index A_i and the production quantity B_i of product i, separated by a space.

Output

Output the number of products whose risk score is K or higher, in a single line.

Sample Input 1

3 100
10 5
20 10
5 30

Sample Output 1

2

Sample Input 2

5 500
15 40
8 100
50 20
30 15
25 25

Sample Output 2

4