Somewhere in the middle of the Great Inspecific Ocean, there is a little-known island called Hippopotamus Island. This peculiar island is in the shape of a square with a side length of L kilometres. There are houses at one kilometre intervals all the way around the island, with the first house on the north-west corner, giving 4L houses on the island in total. Each house may contain some number of people (islanders) or it may be unoccupied. The centre of the island is inhabited by hippopotami who are easily frightened, and so the islanders only ever walk around the coast.
You wish to construct a desalination plant on the island to produce and sell fresh water. You will demolish one of the houses on the island and build the plant in its place. Your plan is to become the sole supplier of fresh water on the island so that every islander will need to travel to you in order to buy their water.
Your calculations say that for each kilometre that an islander must walk, they will buy one litre of water. For example, an islander who must walk four kilometres to get to the desalination plant will buy four litres of water. Note that the islanders can walk around the island either clockwise or counter-clockwise but they will always choose the shorter route to get to their water. If the desalination plant is built on a house containing islanders, you compensate their loss by offering them water for free.
Thinking deviously, you realise that you can sell more water by forcing islanders to walk further. The amount of water you sell is determined by the sum of the distances that each islander must walk to get to your plant.
Consider the above island of side length 3. There are 12 houses on the island, numbered in clockwise order starting from 1 in the north-west corner. Houses 2, 4, 11 and 12 contain 3, 1, 1 and 2 islanders, respectively. If for example, you were to place the desalination plant where house 4 is, you would sell nothing to the one islander you displaced, 3 x 2 = 6 litres to the islanders living in house 2, 2 x 4 = 8 litres to the islanders in house 12, and 1 x 5 = 5 litres to the islanders living in house 11, giving a total of 19 litres of water sold.
Alternately, if the plant was placed on house 8, you would sell 3 x 6 = 18 litres from house 2, 1 x 4 = 4 from house 4, 1 x 3 = 3 from house 11, and 2 x 4 = 8 from house 11, giving a total of 33 litres. This is the maximum amount of water that you can sell.
Your task is, given the size of the island and the locations of the islanders, write a program to determine the maximum amount of water you can sell by strategically locating your desalination plant on the island.
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:
As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. Specifically:
Your program should read from the file islandin.txt. The first line of this file will consist of the integers N and L separated by a single space. Following this will be N lines, each describing an inhabited house. Each of these lines will contain two integers h and p, denoting that house h is inhabited by p islanders (1 ≤ h ≤ 4L, 1 ≤ p ≤ 10,000). The houses will appear in clockwise order around the island, starting with the lowest number. No house will appear in this list more than once.
Your program should write to the file islandout.txt. Your output file should consist of a single integer: the maximum amount of water you can sell.
4 3 2 3 4 1 11 1 12 2
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.