Description

DYY is very interested in machine learning. He has been informed that there are N courses related to machine learning, with each course taking place during a specific time interval [L_i, R_i].

Due to his profound interest in machine learning, he has decided to send his top K students, including Felix Huang, Daniel Huang, Penguin07, Ding Hsuan, and others, to participate in these courses. What is the maximum number of distinct courses that DYY's K students can attend out of the total N courses?

Note: If Penguin07 attends the course during the interval [2, 5], he won't be able to attend the course in the interval [5, 10] due to the overlap at time 5.

Input

The first line of the input contains two integers N and K.

The second line of the input contains N integers L_i, representing the starting time of the courses.

The third line of the input contains N integers R_i, representing the ending time of the courses.

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 100
• 0 ≤ L_i ≤ R_i ≤ 10⁸

Output

Print one integer, the maximum number of distinct courses DYY's students can attend in total.

Remember to print a ‘\n’ at the end of the output.

HINT

Sample 1

One possible answer is to attend the courses during the intervals [0, 2] and [3, 4].

Sample 2

Student 1 attends the courses during the intervals [1, 3] and [4, 7].

Student 2 attends the courses during the intervals [2, 4], [5, 6], and [7, 8].

As a result, two students attend a total of 5 distinct courses.

Sample 3

Due to overlap between the intervals, student 1 can only attend one of them.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

chyen has a strong liking for young magical beings known as "lolis" particularly those who possess the skill of Burst Magic. He has a special fondness for lolis who excel at using Burst Magic. To fulfill this interest, he sets out to teach Burst Magic to all N lolis in his collection. However, he encounters a dilemma: despite acquiring the knowledge of Burst Magic, the lolis lack opportunities to showcase their magical prowess, which leads to a growing sense of discouragement.

In response, chyen makes a decision. He plans to take a group of these lolis on a daring expedition to confront a formidable monster. This monster has a health level of M, and the lolis have the chance to unleash their Burst Magic upon it. Nevertheless, there are specific conditions to consider. Each loli possesses her own magical strength, denoted as m_i, and a measure of bravery, known as the courage value, represented by c_i. A loli can successfully employ Burst Magic to deal damage equal to her magical strength m_i, but only when the monster's health is equal to or less than her courage value c_i. Once a loli uses her Burst Magic, she becomes fatigued and cannot cast the spell again.

Your task is to determine the minimum number of lolis that chyen needs to take along on this adventure to successfully defeat the monster. If it is not possible to defeat the monster under any circumstances, please output -1.

Input

The first line contains two integers, N and M, representing the number of lolis and the monster's health respectively.

The subsequent N lines each provide two numbers, m_i and c_i, indicating the magical strength and courage value of the i-th loli.

• 1 ≤ N, M ≤ 10⁶
• 1 ≤ m_i, c_i ≤ 10⁶

Output

Output the minimum number of lolis required to defeat the monster, or -1 if this task cannot be accomplished.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a universe beyond our own, known as the Pancake Universe, there are N breakfast shop. The coordinates of the i-th breakfast shop are (x_i, y_i). 

The residents of the Pancake Universe have a fondness for pancakes. To facilitate a pancake exchange conference, they have decided to set up pancake teleportation gates between the breakfast shops. Specifically, there is a cost of (x_i - x_j)² + (y_i - y_j)² to set up a gate between the i-th and j-th breakfast shops. Once a gate is set up between two shops, the i-th shop can instantly teleport pancakes to the j-th shop, and vice versa. Once a teleportation gate is built, it can be used any number of times.

Due to financial constraints in the Pancake Universe, please help them calculate the minimum total cost required to ensure that all N breakfast shop can transport pancakes to any other shop through a series of teleportation gates.

Input

The first line contains a positive integer N.

Following that, there are N lines, each containing two integers x_i and yi.

• 1 ≤ N ≤ 1000
• 0 ≤ x_i, y_i ≤ 5000

There could be different shops located at same coordinates.

Output

Output the answer in one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss