Need better approach

I have been tryin this question, http://www.codechef.com/problems/TEAMSEL ,for 2 days now.

I am stuck at an appraoch of order O(nnS),where n is number of elements and S is sum of elements.
Since this question is a subtle variation of standard Balanced Partitioning problem,i guess there must be a O(n*S) approach for this.

Link to my solution is http://www.codechef.com/viewsolution/1632592.

Any help or pointers regarding this is appreciated !