// Artur Kraska, II UWr

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

#include "message.h"
#include "skup.h"


#define forr(i, n)                  for(int i=0; i<(int)n; i++)
#define FOREACH(iter, coll)         for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#define FOR(i, a, b)                for(int i=(int)a; i<=(int)b; i++)
#define FORD(i, a, b)               for(int i=(int)a; i>=(int0b; i--)
#define MP                          make_pair
#define PB                          push_back
#define deb(X)                      X;

#define M 1000000007
#define INF 1000000007

// oznacza ile milisekund bedzie czekac z wyslaniem
#define TIME2 15
// oznacza jakiego czasu nie moze przekroczyc
#define TIME1 10

// CZESC DO TESTOW

#define TESTUJ true
#define cout if(0) cout

bool initialized = 0;

char slowo[107][107];
/*
void initialize()
{
    initialized = 1;
    int x = NumberOfNodes();
    forr(i, x)
        scanf("%s", slowo[i]);
}

int GetInt2(int nr)
{
    if(!initialized)
    {
        initialize();
    }
    int y = GetInt(nr);
    return slowo[MyNodeId()][nr] == '1' ? y : 0;
}

#define GetInt GetInt2
*/
/*

long long NumberOfCompanies() {
  return 1000;
}

long long GetShareCost(long long Id) {
  assert(0 <= Id && Id < 1000);
  return 1000 * 1000 * 1000;
}
*/

// KONIEC TESTOWANIA

using namespace std;

int ILE, NR;
int in[1007], out[1007], in2[1007], out2;
vector <int> kolejnosc;
int min_na_cyklu;

void generuj_kolejnosc_komunikacji()
{
    if(NR != 0 && NR != ILE/2)
    {
        kolejnosc.PB(ILE-NR);
    }
    FOR(i, 1, ILE)
    {
        if(2*NR%ILE != i)
            kolejnosc.PB((i-NR+ILE)%ILE);
    }
/*
    forr(i, ILE-1)
    {
        cout << "kolejnosc: " << kolejnosc[i] << endl;
    }*/
}

void znajdz_wchodzace()
{
    forr(i, ILE)
        if(i != NR)
        {
            PutInt(i, 1);
            Send(i);
        }

    forr(i, ILE)
        if(i != NR)
        {
            Receive(i);
            in[i] = GetInt(i);
            if(in[i])
                cout << " jest krawedz in z " << i << " do " << NR << endl;
        }
}

void powiedz(int nr, bool b)
{
    if(TESTUJ)
    {
        PutLL(nr, b);
        Send(nr);
        return ;
    }

    Receive(nr);
    Send(nr);
    if(b)
    {
        long long start = clock();
        while(clock() - start < TIME2);
    }
    Send(nr);
}

bool zapytaj(int nr)
{
    if(TESTUJ)
    {
        Receive(nr);
        return GetLL(nr);
    }

    Send(nr);
    Receive(nr);
    long long start = clock();
    Receive(nr);
    return clock()-start >= TIME1;
}

void synchronizuj(int i)
{
    if(NR == i)
    {
        cout << "   teraz ja synchronizuje" << endl;
        FOR(j, 0, ILE-1)
            if(j != NR)
            {
                Receive(j);
                cout << "\t\t\t\t\t\t" << " dostalem od " << j << endl;
                GetInt(j);
                GetInt(j);
                GetInt(j);
            }
        FOR(j, 0, ILE-1)
            if(j != NR)
            {
                PutInt(j, 0);
                PutInt(j, 0);
                PutInt(j, 0);
                Send(j);
                cout << "\t\t\t\t\t\t" << " wysylam do " << j << endl;
            }
        cout << "zsynchronizowane" << endl;
    }
    else
    {
        PutInt(i, 0);
        PutInt(i, 0);
        PutInt(i, 0);
        Send(i);
        cout << "\t\t\t\twyslalem do " << i << endl;
        Receive(i);
        cout << "\t\t\t\t odebralem od " << i << endl;
        GetInt(i);
        GetInt(i);
        GetInt(i);
    }
}

void wait()
{
//    long long t = clock();
//    while(clock()-t < 100);
}

void przeslij_wychodzace_za_pomoca(int pom, int pom2)
{
    cout << "wszedlem do przesylania za pomoca " << pom << endl;
    int nr;

    if(pom != NR && NR != pom2) // synchronizowany
    {
        int ile = 0;
        //Send(pom);
        //Send(pom);
        //Receive(pom);
        FOR(i, 0, ILE-1)
            if(i != pom && in[i] && i != pom2)
            {
                ile++;
                PutInt(i, 0);
                Send(i);
            }
        //Send(pom);
        wait();
        if(ile == 0)
        {
            Send(pom);
        }
        while((nr = Receive(-1)) != pom)
        {
//            cout << " mamy krawedz out z " << NR << " do " << nr << endl;
            int x = GetInt(nr);
            if(x == 0)
            {
                out[nr] = 1;
                PutInt(nr, 1);
                Send(nr);
            }
            else // x == 1
            {
                ile--;
                if(ile == 0)
                {
                    Send(pom);
                }
            }
        }
/*        Send(pom);
        wait();
        while((nr = Receive(-1)) != pom)
        {
            cout << " mamy krawedz out z " << NR << " do " << nr << endl;
            out[nr] = 1;
        }*/
    }
    else if(NR == pom) // pierwszy pomocniczy
    {/*
        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Receive(j);
        }
        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Send(j);
        }*/
        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Receive(j);
        }
        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Send(j);
        }
        /*
        wait();

        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Send(j);
        }


        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Receive(j);
        }

        wait();

        forr(j, ILE)
        {
            if(j != pom && j != pom2)
                Send(j);
        }*/
    }

    cout << " wyszedlem od " << pom << endl;
}

void znajdz_wychodzace()
{
    //int pom = 0, nr;//, pom2 = 1, pom3 = 2;

    synchronizuj(5);
    przeslij_wychodzace_za_pomoca(0, 6);

    synchronizuj(6);
    przeslij_wychodzace_za_pomoca(1, 7);

    synchronizuj(7);
    przeslij_wychodzace_za_pomoca(2, 8);

    synchronizuj(8);

    return ;

    // teraz wszystko z i do 0, pomijając krawedz do pom1
//    synchronizuj(6);
/*
    if(pom == NR) // synchronizowany
    {
        Send(pom2);
        FOR(i, 0, ILE-1)
            if(i != pom && i != pom2 && in[i])
            {
                Send(i);
            }
        Send(pom2);
        while((nr = Receive(-1)) != pom2)
        {
            cout << " mamy krawedz out z " << NR << " do " << nr << endl;
            out[nr] = 1;
        }
    }
    else  if(NR != pom && NR != pom2) // pierwszy pomocniczy
    {
        Send(pom2);
        if(in[pom])
            Send(pom);
        Send(pom2);
        Receive(pom2);
    }
    else // NR == pom2
    {
        forr(j, ILE)
        {
            if(j != pom2)
                Receive(j);
        }
        forr(j, ILE)
        {
            if(j != pom2)
                Receive(j);
        }

        wait();

        forr(j, ILE)
        {
            if(j != pom2)
                Send(j);
        }
    }
    synchronizuj(7);
*//*
    // teraz krawedzie pom-pom2
    if(NR == pom || NR == pom2)
    {
        int drugi = (NR == pom ? pom2 : pom);
        Send(pom3);
        if(in[drugi])
            Send(drugi);
        Send(pom3);
        while((nr = Receive(-1)) != pom3)
        {
            cout << " mamy krawedz out z " << NR << " do " << nr << endl;
            out[nr] = 1;
        }
    }
    else if(NR == pom3)
    {
        Receive(pom);
        Receive(pom2);
        Receive(pom);
        Receive(pom2);
        wait();
        Send(pom2);
        Send(pom);
    }
*/
//    synchronizuj(4);

/*
    forr(i, ILE)
    {
        synchronizuj(i);

        int pom = (i+1)%ILE, pom2 = (i+2)%ILE, nr;
        if(i == NR) // synchronizowany
        {
            Send(pom);
            while((nr = Receive(-1)) != pom)
            {
                cout << " mamy krawedz out z " << NR << " do " << nr << endl;
                out[nr] = 1;
            }
            Send(pom2);
            while((nr = Receive(-1)) != pom2)
            {
                cout << " mamy krawedz out z " << NR << " do " << nr << endl;
                out[nr] = 1;
            }
        }
        else if(NR == pom) // pierwszy pomocniczy
        {
            Receive(i);
            forr(j, ILE)
            {
                if(j != i && j != pom)
                    Receive(j);
            }
            Send(i);

            if(in[i])
                Send(i);
            Send(pom2);
        }
        else if(NR == pom2) // drugi pomocniczy
        {
            if(in[i])
            {
                Send(i);
            }
            Send(pom);

            Receive(i);
            Receive(pom);
            Send(i);
        }
        else  // pozostale
        {
            if(in[i])
            {
                Send(i);
            }
            Send(pom);
        }
    }
    synchronizuj(4);

*/
/*    forr(i, ILE-1)
    {
        int nr = kolejnosc[i];
        if(NR < nr)
        {
            powiedz(nr, in[nr]);
            out[nr] = zapytaj(nr);
        }
        else
        {
            out[nr] = zapytaj(nr);
            powiedz(nr, in[nr]);
        }
        if(out[nr])
        {
            cout << "mam krawedz do " << nr << " :)" << endl;
        }
        else
        {
//            cout << "nie mam krawedzi do " << nr << " :(" << endl;
        }
    }*/
}

void wybierz_najmniejsza_wychodzaca()
{
    out2 = -1;
    forr(i, ILE)
        if(out[i])
        {
            out2 = i;
            cout << " out2 z " << NR << " to " << out2 << endl;
            return ;
        }
}

void filtruj_najmniejsze_wchodzace()
{
    cout << " filtruje" << endl;
    forr(i, ILE)
    {
        if(i != NR)
        {
            PutInt(i, out2+1);
            cout << "    wysylam " << out2+1 << " do " << i << endl;
            Send(i);
        }
    }

    forr(i, ILE)
    {
        if(i != NR)
        {
            cout << "      odbieram od " << i << endl;
            Receive(i);
            int x = GetInt(i);
            if(x == NR+1)
            {
                cout << "   mam in2 do " << i << endl;
                in2[i] = 1;
            }
//            cout << "     " << i << " przyslal mi " << x << ", czyli in2[" << i << "] = " << in2[i] << endl;
        }
    }
    cout << " przefiltrowalem" << endl;
    /*
    forr(i, ILE-1)
    {
        int nr = kolejnosc[i];
        if(NR < nr)
        {
            powiedz(nr, nr == out2);
            in2[nr] = zapytaj(nr);
            cout << "\t\t\t\t\tmowie do " << nr << ", ze " << (nr == out2) << endl;
            cout << "\t\t\t\t\t" << nr << " powiedzial mi, ze " << in2[nr] << endl;
        }
        else
        {
            in2[nr] = zapytaj(nr);
            powiedz(nr, nr == out2);
            cout << "\t\t\t\t\t" << nr << " powiedzial mi, ze " << in2[nr] << endl;
            cout << "\t\t\t\t\tmowie do " << nr << ", ze " << (nr == out2) << endl;
        }
        if(in2[nr])
        {
            cout << "mam krawedz wchodzaca2 z " << nr << " :)" << endl;
        }
        else
        {
//            cout << "nie mam krawedzi wchodzacej2 z " << nr << " :(" << endl;
        }
    }*/
}

int znajdz_min_na_cyklu()
{
    cout << "  szukam min na cyklu" << endl;
    int minn = NR, b;
    forr(c, ILE+2)
    {
        if(out2 >= 0)
        {
            PutInt(out2, minn);
            Send(out2);
        }
        minn = INF;
        forr(i, ILE)
            if(in2[i])
            {
                Receive(i);
                b = GetInt(i);
                minn = min(minn, b);
            }
        if(minn < INF)
            minn = min(minn, NR);
    }
    return minn;
}

void przeslij_i_wypisz()
{
//    cout << "\t\t zaczynam przesylac wynik" << endl;
    cout << "  zaczynam przesylanie " << endl;
    int n;
    vector <int> res;
    n = NumberOfCompanies();
    forr(i, n)
        res.PB(-GetShareCost(i));

    forr(i, ILE)
        if(in2[i] && i != min_na_cyklu)
        {
//            cout << " odbieram od " << i << endl;
            Receive(i);
            n = GetInt(i);
//            cout << "n: " << n << endl;
            forr(j, n)
                res.PB(GetInt(i));
        }

    cout << "min na cyklu: " << min_na_cyklu << ", out2: " << out2 << endl;
    if(NR != min_na_cyklu && out2 != -1)
    {
        PutInt(out2, res.size());
        forr(i, res.size())
            PutInt(out2, res[i]);
        Send(out2);
    }
    else
    {
        cout << "wynik ma " << res.size() << " elementow" << endl;
        sort(res.begin(), res.end());
        long long result = 0;
        forr(i, res.size())
        {
            result += -(i+1)*(long long)res[i];
        }
        printf("%lld\n", result);
    }
}

int main()
{
    ILE = NumberOfNodes();
    NR = MyNodeId();

    znajdz_wchodzace();
    generuj_kolejnosc_komunikacji();
    znajdz_wychodzace();
    wybierz_najmniejsza_wychodzaca();
    filtruj_najmniejsze_wchodzace();
    min_na_cyklu = znajdz_min_na_cyklu();
    przeslij_i_wypisz();

    return 0;
}