1) greedy works here, although it's not that much obvious how *correct* greedy should look like
2) 5th test case, that didn't pass for me:

12
-3 10
-2 8
-1 16
0 0

Edited by author 17.02.2018 04:30