U520663 监考老师

期末考试来临，大家都想让本校监考老师过来，好~~抄袭答案~~平复心情。不过，出题人的狡猾监考老师过来监考，那...谁说这监考的不好了，这监考可真是太好了！

**注：该题目为出题人的狡猾监考老师的狡猾真实事件改编。** 众所都知，AI_god 马上迎来一年两度不知道重不重要也要被老师说成很重要的期末考试！！！ 而且，本次期末考试由外校狡猾的监考老师来监考！本次期末考试采用分组非相同考点的形式考试。具体来说，AI_god 的班级有 $N$ 位学生。而学校有 $T$ 间教室，每间教室都要坐一个学生。所以， $T \le N$。 而现在，狡猾的监考老师知道，我需要让这个学校的成绩不如我们学校！所以，他希望通过分班从而让总分最大的班级的总分最小。但是，AI_god 的校长 yuhaotian000 也知道，我们不能让监考老师得逞！ 所以，我们有如下的分班格式： 每个学生都有一个学号。在输入时，若 $P=0$ ，则学号已经帮你确定好，若 $P=1$ ，则需要你自己来排版学号。第 $i$ 个人的学号为 $i$ ，成绩为 $S_i$ 。 接下来，监考老师可以将一些学号连续的学生分为一组，即他们是一个班级。例如说有 $5$ 个学生，我们想将其分为 $2$ 组（有 $2$ 个班），我们就可以让学号为 $1、2$ 的学生为一组，学号为 $3、4、5$ 的学生为一组。注意，不能有学生不在组里，但是可以一个人一组。第 $t$ 组会进入到第 $t$ 个班级里。 现在，你就是这个狡猾的监考老师，你想让总分最大的班级的总分最少。所以，最少的总分应该是多少？由于你很狡猾，所以你不能漏出马脚，所以我们不想知道如何分组，只好知道最少的总分就好了。

无

无

对于样例 $1$，我们的最好分组是将组分为 $[97,23,100]$ 和 $[96,90]$。在这时，总分最大的班级为班级 $1$，总分为 $220$ 分，这是让总分最大的班级的总分最少的最好办法。狡猾的老师得逞啦！ 对于 $20\%$ 的数据， $P=1,1 \le T \le N \le 7,10 \le S_i \le 50$ 。 对于其余 $80\%$ 的数据，$1 \le T \le N \le 5 \times 10^4,10 \le S_i(1 \le i \le N) \le 1,000,000，P=0$。