Statement

The IKPC is right around the corner. The kindergarten teacher, Theresa, wants to form some teams for the competition. There are N children in her class, and she wants to form exactly K teams. The children are sitting along a line, numbered from 0 to N-1, according to their position in the line. Child i has a team play factor A_i and a programming skill B_i. Each team must have at least one member, and no child can be assigned to multiple teams. Children 0 < i_1 < i_2 < … < i_l < N (for some l>0) can form a team if for each 1 < p < l the following conditions hold: (1) A_i_p < A_i_p+1, and (2) there is no child with index i_p < x < i_p+1 such that A_i_p < A_x. The strength of a team formed this way is B_i_1 + B_i_2 + … + B_i_l. Your task is to find the maximum possible sum of team strengths that Theresa can achieve by forming exactly K teams!