For Bessie the cow’s birthday, Farmer John has given her free reign over one of his best fields to eat grass.

The field is covered in N patches of grass (1 \le N \le 1000), conveniently numbered 1\ldots N, that each have a distinct quality value. If Bessie eats grass of quality Q, she gains Q units of energy. Each patch is connected to up to 10 neighboring patches via bi-directional paths, and it takes Bessie E units of energy to move between adjacent patches (1 \le E \le 1,000,000). Bessie can choose to start grazing in any patch she wishes, and she wants to stop grazing once she has accumulated a maximum amount of energy.

Unfortunately, Bessie is a picky bovine, and once she eats grass of a certain quality, she’ll never eat grass at or below that quality level again! She is still happy to walk through patches without eating their grass; in fact, she might find it beneficial to walk through a patch of high-quality grass without eating it, only to return later for a tasty snack.

Please help determine the maximum amount of energy Bessie can accumulate.

[Problem credits: Austin Anderson and Brian Dean, 2015]

#3933 upload 2 done 1 how_to_reg 1

Bessie's Birthday Buffet timer 1s memory 256MB

#3933

Bessie's Birthday Buffet 1s 256MB