Expensive Chair Stacking

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.2s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

To make some extra pocket money, Angie got a job stacking chairs!

Today, she was assigned a room to stack chairs in. The room begins with N chairs spread all around a M \times M room, with each chair at the integer coordinates (x_i, y_i). Angie's task is to stack all the chairs onto an integer coordinate (x_e, y_e) in the room.

However, her boss has a very odd method of payment- for each chair stacked, he will pay \$x where x denotes the Manhattan distance* from the start to end locations of the chair. Being an economic individual, Angie wants to know the maximum amount of money she can make from the room. Can you help her figure it out?

*The manhattan distance between points (x_1, y_1) and (x_2, y_2) is |x_2-x_1|+|y_2-y_1|


For all subtasks:

1 \le x_i, y_i, x_e, y_e \le M

Subtask 1 [20%]

1 \le N, M \le 500

Subtask 2 [20%]

1 \le N \le 10^6

1 \le M \le 50

Subtask 2 [30%]

1 \le N \le 10^5

1 \le M \le 10^9

Subtask 3 [30%]

1 \le N \le 3 \times 10^6

1 \le M \le 10^9

Input Specification

The first line contains the space separated integers N and M.

The next N lines each contain the two space separated integers (x_i, y_i).

Output Specification

Output one integer, the maximum amount of money she can make.

Sample Input

5 10
3 8
9 1
10 2
4 5
7 8

Sample Output



Moving all the chairs to (1, 10) yields the maximum profit of \$54


There are no comments at the moment.