## Expensive Chair Stacking

View as PDF

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

Author:
Problem type

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 chairs spread all around an room, with each chair at the integer coordinates . Angie's task is to stack all the chairs onto an integer coordinate in the room.

However, her boss has a very odd method of payment - for each chair stacked, he will pay where 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 and is .

#### Input Specification

The first line contains the space separated integers and .

The next lines each contain the two space separated integers .

#### 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

54

#### Explanation

Moving all the chairs to yields the maximum profit of .