Bessie's Birthday Buffet timer 1초 memory 256MB

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]