这是平凡的一天，啪啪颜起床了！啪啪颜有很多事情要做，第i件事情花费时间t[i]，其中有些事情能同时做，有些则不能。我们把能同时做的事称为“1事件”，不能的则称为“0事件”。做“0事件”的任意片段时间内，可以选择不做或做一件“1事件”。只做一件“1事件”时，可以选择在做一件“1事件”。求做完所有事件所需的最短时间。

输入第一行有一个数n(0

输出

一个数，即花费的最小时间。

样例输入

7
1 1
1 2
1 5
0 3
0 3
0 3
0 1

样例输出

9

来源/分类

啪啪颜的一天之一，适合会循环和排序的同学。 

[提交] [状态]