Force Fields

A physics and biology laboratory studies how radiation affects plants when the radiation passes through force fields.

The experimental setup has a square platform of size 10^9 × 10^9 filled with fertile soil. A radiation source is mounted above the platform. Between the radiation source and the platform, n force fields can be switched on.

The force field generator is mounted above the point (0, 0). The i-th force field is a rectangle whose sides are parallel to the borders of the platform, with two opposite corners at (0, 0) and (x_i, y_i).

The experiment will study how radiation affects plants when the radiation passes through k force fields. Exactly k of the given n fields must be chosen for the experiment. The scientists want to choose the fields so that the area of the part of the platform lying under all k chosen fields is as large as possible.

Given the integers n and k and the descriptions of the n force fields, write a program that determines which k force fields to choose so that the area covered by all k chosen fields is as large as possible, and outputs that area.

The first line contains the integers n and k (1 ≤ k ≤ n ≤ 200,000), the total number of force fields and the number of force fields to choose for the experiment.

The next n lines each contain two integers x_i, y_i (1 ≤ x_i, y_i ≤ 10^9), the coordinates of the corner of the i-th force field rectangle that is farther from the origin.

Output a single integer: the maximum area of the region.

Figure 1 shows the five force fields given in the input. The optimal way to choose three of them for the experiment is shown in Figure 2.

Figure 1. The force fields in the sample input.

Figure 2. The optimal choice of three force fields out of five in this sample.