Minimize Bounding Square

AtCoder

IDabc330_f

Time3000ms

Memory256MB

Difficulty—

There are $N$ points labeled $1, 2, \dots, N$ on the $xy$\-plane. Point $i$ is located at coordinates $(X_i, Y_i)$. You can perform the following operation between $0$ and $K$ times, inclusive. * First, choose one of the $N$ points. Let $k$ be the selected point, and assume it is currently at $(x, y)$. * Next, choose and execute one of the following four actions: * Move point $k$ along the $x$\-axis by $+1$. The coordinates of point $k$ become $(x+1, y)$. * Move point $k$ along the $x$\-axis by $-1$. The coordinates of point $k$ become $(x-1, y)$. * Move point $k$ along the $y$\-axis by $+1$. The coordinates of point $k$ become $(x, y+1)$. * Move point $k$ along the $y$\-axis by $-1$. The coordinates of point $k$ become $(x, y-1)$. * It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates. After all your operations, draw one square that includes all the $N$ points inside or on the circumference, with each side parallel to the $x$\- or $y$\-axis. Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points. **In particular, if all points can be made to exist at the same coordinates, the answer is considered to be $0$.** ## Constraints * All input values are integers. * $1 \le N \le 2 \times 10^5$ * $0 \le K \le 4 \times 10^{14}$ * $0 \le X_i, Y_i \le 10^9$ ## Input Input is given from Standard Input in the following format: $N$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$ [samples]

Samples

Input #1

Output #1

3

The figure below illustrates this case with the horizontal $x$\-axis and the vertical $y$\-axis.
![image](https://img.atcoder.jp/abc330/932178d158b342b9bda6bdc72b439f0e.png)
For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of $3$, and this can be shown to be the minimum value.

Input #2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Output #2

0

All points already exist at the same coordinates from the beginning.  
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is $0$.

Input #3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

Output #3

484373824

API Response (JSON)

{
  "problem": {
    "name": "Minimize Bounding  Square",
    "description": {
      "content": "There are $N$ points labeled $1, 2, \\dots, N$ on the $xy$\\-plane. Point $i$ is located at coordinates $(X_i, Y_i)$.   You can perform the following operation between $0$ and $K$ times, inclusive. *  ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc330_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ points labeled $1, 2, \\dots, N$ on the $xy$\\-plane. Point $i$ is located at coordinates $(X_i, Y_i)$.  \nYou can perform the following operation between $0$ and $K$ times, inclusive.\n\n*  ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments