//author divesh uttamchandani
//EQGIFTS
//logic sorted the difference of pairs as it is the one which matters now problem reduces to assigning +ve
//negetive signs such that the sum is as close to zero or divide the differences in two sets +ve/-ve such
//the sum of +ve parts is closest to sum of negetive parts
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef long long int lli;
#define loop(i,t) for(i=0;i<t;++i)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
int N,i,s=0,s1,A,B;
vector<int> dp(23000,-1); //dp[i] contains the max sum attainable up to i;
vector<int> v; //contains the sorted elements
int solve(int i) //gives sum attainable upto i
{
if(i==0)
return 0;
if (dp[i]==-1)
{
int j;
for(j=0;v[j]<=i;j++) //first iterate over the eligible elements from the array;
{
dp[i]=max((solve(i-v[j])+v[j]),dp[i]);
}
}
return dp[i];
}
int main()
{
dp[0]=0;
cin>>N;
loop(i,N)
{
cin>>A>>B;
if(A!=B)
v.pb(abs(A-B));
s+=abs(A-B);
}
sort(all(v));
s1=s/2; //this is the required sum;
cout<<abs(s-solve(s1)-s1);
return 0;
}
Ly9hdXRob3IgZGl2ZXNoIHV0dGFtY2hhbmRhbmkKLy9FUUdJRlRTCi8vbG9naWMgc29ydGVkIHRoZSBkaWZmZXJlbmNlIG9mIHBhaXJzIGFzIGl0IGlzIHRoZSBvbmUgd2hpY2ggbWF0dGVycyBub3cgcHJvYmxlbSByZWR1Y2VzIHRvIGFzc2lnbmluZyArdmUKLy9uZWdldGl2ZSBzaWducyBzdWNoIHRoYXQgdGhlIHN1bSBpcyBhcyBjbG9zZSB0byB6ZXJvIG9yIGRpdmlkZSB0aGUgZGlmZmVyZW5jZXMgaW4gdHdvIHNldHMgK3ZlLy12ZSBzdWNoCi8vdGhlIHN1bSBvZiArdmUgcGFydHMgaXMgY2xvc2VzdCB0byBzdW0gb2YgbmVnZXRpdmUgcGFydHMKCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3Rvcjx2aT4gdnZpOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbGk7CiNkZWZpbmUgbG9vcChpLHQpIGZvcihpPTA7aTx0OysraSkKI2RlZmluZSBzeihhKSBpbnQoKGEpLnNpemUoKSkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBhbGwoYykgKGMpLmJlZ2luKCksKGMpLmVuZCgpCiNkZWZpbmUgdHIoYyxpKSBmb3IodHlwZW9mKChjKS5iZWdpbigpKSBpID0gKGMpLmJlZ2luKCk7IGkgIT0gKGMpLmVuZCgpOyBpKyspCiNkZWZpbmUgcHJlc2VudChjLHgpICgoYykuZmluZCh4KSAhPSAoYykuZW5kKCkpCiNkZWZpbmUgY3ByZXNlbnQoYyx4KSAoZmluZChhbGwoYykseCkgIT0gKGMpLmVuZCgpKQppbnQgTixpLHM9MCxzMSxBLEI7CnZlY3RvcjxpbnQ+IGRwKDIzMDAwLC0xKTsgIC8vZHBbaV0gY29udGFpbnMgdGhlIG1heCBzdW0gYXR0YWluYWJsZSB1cCB0byBpOwp2ZWN0b3I8aW50PiB2OyAgICAgICAgICAgICAvL2NvbnRhaW5zIHRoZSBzb3J0ZWQgZWxlbWVudHMKCmludCBzb2x2ZShpbnQgaSkgICAgLy9naXZlcyBzdW0gYXR0YWluYWJsZSB1cHRvIGkKewogICAgaWYoaT09MCkKICAgICAgICByZXR1cm4gMDsKCiAgICBpZiAoZHBbaV09PS0xKQogICAgewogICAgICAgIGludCBqOwogICAgICAgIGZvcihqPTA7dltqXTw9aTtqKyspICAgIC8vZmlyc3QgaXRlcmF0ZSBvdmVyIHRoZSBlbGlnaWJsZSBlbGVtZW50cyBmcm9tIHRoZSBhcnJheTsKICAgICAgICB7CiAgICAgICAgICAgIGRwW2ldPW1heCgoc29sdmUoaS12W2pdKSt2W2pdKSxkcFtpXSk7CiAgICAgICAgfQogICAgfQogICAgICAgIHJldHVybiBkcFtpXTsKfQoKaW50IG1haW4oKQp7CiAgICBkcFswXT0wOwogICAgY2luPj5OOwogICAgbG9vcChpLE4pCiAgICB7CiAgICAgICAgY2luPj5BPj5COwogICAgICAgIGlmKEEhPUIpCiAgICAgICAgdi5wYihhYnMoQS1CKSk7CiAgICAgICAgcys9YWJzKEEtQik7CiAgICB9CiAgICBzb3J0KGFsbCh2KSk7CiAgICBzMT1zLzI7IC8vdGhpcyBpcyB0aGUgcmVxdWlyZWQgc3VtOwogICAgY291dDw8YWJzKHMtc29sdmUoczEpLXMxKTsKCXJldHVybiAwOwp9