{"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*   First, choose one of the $N$ points. Let $k$ be the selected point, and assume it is currently at $(x, y)$.\n*   Next, choose and execute one of the following four actions:\n    *   Move point $k$ along the $x$\\-axis by $+1$. The coordinates of point $k$ become $(x+1, y)$.\n    *   Move point $k$ along the $x$\\-axis by $-1$. The coordinates of point $k$ become $(x-1, y)$.\n    *   Move point $k$ along the $y$\\-axis by $+1$. The coordinates of point $k$ become $(x, y+1)$.\n    *   Move point $k$ along the $y$\\-axis by $-1$. The coordinates of point $k$ become $(x, y-1)$.\n*   It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.\n\nAfter 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.  \nFind 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.\n**In particular, if all points can be made to exist at the same coordinates, the answer is considered to be $0$.**\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $0 \\le K \\le 4 \\times 10^{14}$\n*   $0 \\le X_i, Y_i \\le 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$\\vdots$\n$X_N$ $Y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc330_f","tags":[],"sample_group":[["6 5\n2 0\n5 2\n0 3\n3 2\n3 4\n1 5","3\n\nThe figure below illustrates this case with the horizontal $x$\\-axis and the vertical $y$\\-axis.\n![image](https://img.atcoder.jp/abc330/932178d158b342b9bda6bdc72b439f0e.png)\nFor 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."],["4 400000000000000\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000","0\n\nAll points already exist at the same coordinates from the beginning.  \nFor example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is $0$."],["10 998244353\n489733278 189351894\n861289363 30208889\n450668761 133103889\n306319121 739571083\n409648209 922270934\n930832199 304946211\n358683490 923133355\n369972904 539399938\n915030547 735320146\n386219602 277971612","484373824"]],"created_at":"2026-03-03 11:01:14"}}