P3016 [USACO11FEB] The Triangle S

For her spectacular milk output for the previous month, Farmer John has awarded Bessie a prize -- with a twist. He has given her a triangular grid with N (1

\* Line 1: Two space-separated integers: N and K \* Lines 2..N+1: Line i+1 will contain i space-separated integers: v\_ij

\* Line 1: The maximum number of coins that Bessie can receive (or, if negative, the best she can do for her loss).