On your quest to make a deserted island your new home, your friend Isabelle asks you to update the island's scenery with some furniture and flowers in order to raise the island's star rating. She shows you the catalog that has a total of \(n\) flower and furniture items with their costs \(c_i\) and wow-factor values \(w_i\). Isabelle then asks you to select at most \(k\) items from the catalog that will result in the highest total scenery value \(S\).

The total scenery value \(S\) of \(k\) items is calculated by multiplying the cost \(c_i\) of each item with the lowest wow-factor value \(w_{lowest}\) of the set of \(k\) selected items and taking their summation. For example, for the set of \(k\) items [Pink Rose, Black Gazebo, Blue Arcade Chair] with \(w_i\) values [5, 15, 2] and \(c_i\) values [60, 3000, 500] respectively, the lowest wow-factor value \(w_{lowest}\) is 2. So, the total scenery value \(S\) is calculated as \(2 \cdot (60 + 3000 + 500) = 7120\).

Given the total scenery value \(S\), island star rating \(R\) is calculated as follows:

• if \(S \lt 10^4\), then \(R\) is 1 star,
• if \(10^4 \le S < 5 \cdot 10^4\), then \(R\) is 2 stars,
• if \(5 \cdot 10^4 \le S < 10^6\), then \(R\) is 3 stars,
• if \(10^6\le S < 5 \cdot 10^6\), then \(R\) is 4 stars,
• if \(S \ge 5 \cdot 10^6\), then \(R\) is 5 stars.

Given a catalog of \(n\) items and an item limit of \(k\), your task is to report the highest possible star rating you can achieve. You can select at most \(k\) items.

Input

The first line contains two integers, \(n\) and \(k\), the number of items in the catalog and the item limit.

Each of the next \(n\) lines contains two integers \(c_i\) and \(w_i\), cost and wow-factor values of \(i^{th}\) item respectively.

• \(1 \le k \lt n \le 2 \cdot 10^5\)
• \(1 \le c_i, w_i \le 10^6\)

Output

Print the highest possible star rating \(R\) that can be achieved with the given catalog and item limitation.

Example

Input 1:

4 3
10 1
60 5
500 2
3000 15

Output 1:

2 stars

Explanation

Input 1: The highest scenery value can be achieved by only selecting the \(4^{th}\) item which has 3000 and 15 as \(c_i\) and \(w_i\) values respectively.

The total scenery value \(S\) is calculated as \(15 \cdot 3000 = 45000\), which results in a star rating \(R\) of 2 stars.