cf----2019-10-08（Turn the Rectangles，Mouse Hunt，Elections）

一场游戏一场空，最终 最初都由我掌控，好像一身从容，不曾有狼狈伤痛，可深夜一个人该如何相拥？ 

There are nn rectangles in a row. You can either turn each rectangle by 9090 degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that you can turn any number of rectangles, you also can turn all or none of them. You can not change the order of the rectangles.

Find out if there is a way to make the rectangles go in order of non-ascending height. In other words, after all the turns, a height of every rectangle has to be not greater than the height of the previous rectangle (if it is such).

Input

The first line contains a single integer nn (1≤n≤1051≤n≤105) — the number of rectangles.

Each of the next nn lines contains two integers wiwi and hihi (1≤wi,hi≤1091≤wi,hi≤109) — the width and the height of the ii-th rectangle.

Output

Print "YES" (without quotes) if there is a way to make the rectangles go in order of non-ascending height, otherwise print "NO".

You can print each letter in any case (upper or lower).

Examples

input

Copy

3
3 4
4 6
3 5

output

Copy

YES

input

Copy

2
3 4
5 5

output

Copy

NO

Note

In the first test, you can rotate the second and the third rectangles so that the heights will be [4, 4, 3].

In the second test, there is no way the second rectangle will be not higher than the first one.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
struct node
{
    int w;
    int h;
} p[100010];
int n,flag=1;
int main()
{
    cin>>n;
    p[0].h=inf;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i].w>>p[i].h;
        if(max(p[i].w,p[i].h)<=p[i-1].h)
            p[i].h=max(p[i].w,p[i].h);
        else if(min(p[i].w,p[i].h)<=p[i-1].h)
            p[i].h=min(p[i].w,p[i].h);
        else if(min(p[i].w,p[i].h)>p[i-1].h)
            flag=0;
    }
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;

Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80%80% of applicants are girls and majority of them are going to live in the university dormitory for the next 44 (hopefully) years.

The dormitory consists of nn rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number ii costs cici burles. Rooms are numbered from 11 to nn.

Mouse doesn't sit in place all the time, it constantly runs. If it is in room ii in second tt then it will run to room aiai in second t+1t+1 without visiting any other rooms inbetween (i=aii=ai means that mouse won't leave room ii). It's second 00 in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.

That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that's not the case, mouse can be in any room from 11 to nn at second 00.

What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?

Input

The first line contains as single integers nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of rooms in the dormitory.

The second line contains nn integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤1041≤ci≤104) — cici is the cost of setting the trap in room number ii.

The third line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) — aiai is the room the mouse will run to the next second after being in room ii.

Output

Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.

Examples

input

Copy

5
1 2 3 2 10
1 3 4 3 3

output

Copy

3

input

Copy

4
1 10 2 10
2 4 2 2

output

Copy

10

input

Copy

7
1 1 1 1 1 1 1
2 2 2 3 6 7 6

output

Copy

2

Note

In the first example it is enough to set mouse trap in rooms 11 and 44. If mouse starts in room 11 then it gets caught immideately. If mouse starts in any other room then it eventually comes to room 44.

In the second example it is enough to set mouse trap in room 22. If mouse starts in room 22 then it gets caught immideately. If mouse starts in any other room then it runs to room 22 in second 11.

Here are the paths of the mouse from different starts from the third example:

• 1→2→2→…1→2→2→…;
• 2→2→…2→2→…;
• 3→2→2→…3→2→2→…;
• 4→3→2→2→…4→3→2→2→…;
• 5→6→7→6→…5→6→7→6→…;
• 6→7→6→…6→7→6→…;
• 7→6→7→…7→6→7→…;

So it's enough to set traps in rooms 22 and 66.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,a[200010],b[200010],jg,vis[200010],tt=0;
int main(void)
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<=n; i++)
        scanf("%d",&b[i]);
    for(int i=1; i<=n; i++)
    {
        if(vis[i])
            continue;
        int j=i;
        tt++;
        while(1)
        {
            vis[j]=tt;
            j=b[j];
            if(vis[j]==tt)
            {
                int ct=j;
                int t=b[ct];
                int tmp=a[ct];
                while(t!=ct)
                {
                    tmp=min(tmp,a[t]);
                    t=b[t];
                }
                jg+=tmp;
                break;
            }
            else if(vis[j] && vis[j]!=tt)
                break;
        }
    }
    printf("%d\n",jg);
    return 0;
}

As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon.

Elections are coming. You know the number of voters and the number of parties — nn and mm respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give ii-th voter cicibytecoins you can ask him to vote for any other party you choose.

The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.

Input

The first line of input contains two integers nn and mm (1≤n,m≤30001≤n,m≤3000) — the number of voters and the number of parties respectively.

Each of the following nn lines contains two integers pipi and cici (1≤pi≤m1≤pi≤m, 1≤ci≤1091≤ci≤109) — the index of this voter's preferred party and the number of bytecoins needed for him to reconsider his decision.

The United Party of Berland has the index 11.

Output

Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.

Examples

input

Copy

1 2
1 100

output

Copy

0

input

Copy

5 5
2 100
3 200
4 300
5 400
5 900

output

Copy

500

input

Copy

5 5
2 100
3 200
4 300
5 800
5 900

output

Copy

600

Note

In the first sample, The United Party wins the elections even without buying extra votes.

In the second sample, The United Party can buy the votes of the first and the fourth voter. This way The Party gets two votes, while parties 33, 44 and 55 get one vote and party number 22 gets no votes.

In the third sample, The United Party can buy the votes of the first three voters and win, getting three votes against two votes of the fifth party.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define mod 1e9+7
typedef long long ll;
using namespace std;
ll inf=1e18+7;
vector<pair <int,int> >a,G[40010];
bool vis[40010];
int n,m,w,xh,ct;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&xh,&w);
        if(xh==1)
            ct++;
        else
        {
            a.push_back(make_pair(w,i));
            G[xh].push_back(make_pair(w,i));
        }
    }
    sort(a.begin(),a.end());
    for(int i=1; i<=m; i++)
        sort(G[i].begin(),G[i].end());
    ll mi=inf;
    for(int k=0; k<=n-1; k++)
    {
        memset(vis,0,sizeof(vis));
        ll sum=0;
        int t=0;
        for(int i=2; i<=m; i++)
        {
            int p=0;
            while(G[i].size()-p>k)
            {
                sum+=G[i][p].first;
                vis[G[i][p].second]=1;
                p++;
            }
            t+=p;
        }
        int jg=0;
        while(t+ct<=k)
        {
            if(!vis[a[jg].second])
            {
                sum+=a[jg].first;
                t++;
                vis[a[jg].second]=1;
            }
            jg++;
        }
        mi=min(mi,sum);
    }
    printf("%I64d\n",mi);
    return 0;
}