I think tests for this problem are weak.
For example, there is no tests like
1000
2 2 2
1 1 1
4 4 4
3 3 3
...
1000 1000 1000
999 999 99

My program works slowly on this test (nearly 0.5sec) but it's fly like a wind on submission