集训第四周（高效算法设计）I题 （贪心）

Description

Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is t and its pages' width is equal to w. The thickness of each book is either 1 or 2. All books have the same page heights.

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.

Input

The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers t and w denoting the thickness and width of the i-th book correspondingly, (1 ≤ t ≤ 2, 1 ≤ w ≤ 100).

Output

On the only line of the output print the minimum total thickness of the vertical books that we can achieve.

Sample Input

Input

5
1 12
1 3
2 15
2 5
2 1

Output

5

Input

3
1 10
2 1
2 4

Output

3

如题，书你可以竖着放，横着放（必须放在竖着放的书的上面），要求竖着放的书所造成的厚度越小越好
既然书的厚度只有1 2两种情况，那么就可以准备两个数组一个放厚度为1的一个放厚度为2的，最后贪心，先对两个数组排序，长度大的在前面，因为你竖着放的话，长度多大毫无关系，横着放的话，长度就很是问题了。然后你就可以从小到大开始枚举，选出几本放在下面，计算出这几本的厚度，再把余下的书都默认放在上面，计算出它们的长度，如果厚度大于等于长度，退出循环，输出答案

#include"iostream"

#include"algorithm"

using namespace std;

const int maxn=100+10;

int n;

int f,fb;

int a[maxn];

int b[maxn];

bool cmp(int a1,int a2)

{

    return a1>a2;

}

int suma[maxn],sumb[maxn];

void Init()

{

    int tt,ttt;

     f=fb=0;

    for(int i=0;i<n;i++)

    {

        cin>>tt>>ttt;

        if(tt==1) a[f++]=ttt;

        if(tt==2)  b[fb++]=ttt;

    }

    sort(a,a+f,cmp);

    sort(b,b+fb,cmp);

    suma[0]=0;sumb[0]=0;

    for(int i=1;i<=f;i++) suma[i]=a[i-1]+suma[i-1];

    for(int i=1;i<=fb;i++) sumb[i]=b[i-1]+sumb[i-1];

}

void Work()

{

int ans=100000;

for(int i=0;i<=f;i++)

for(int j=0;j<=fb;j++)

{

    int thick=i+j*2;

    int width=suma[f]-suma[i]+sumb[fb]-sumb[j];

    if(thick>=width&&ans>thick) ans=thick;

}

cout<<ans<<endl;

}

int main()

{

    cin>>n;

    Init();

    Work();

    return 0;

}