#include <cstring>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define ABS(a) ((a)<0?(-(a)):(a))
#define CS while(cases())
#define I(n) int n = gi()
#define II(n) n = gi()
#define L(n) ll n = gli()
#define LL(n) n = gli()
#define F(i, n) for (int i = 0; i < n; i++)
#define Fa(n, a) for (int i = 0; i < n; i++) a[i] = gi()
#define R(i, n) for (int i = n-1; i >= 0; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

template<class T>
T gcd(T a, T b) {
    return (b == 0 ? a : gcd(b, a%b));
}

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int cases() {
    static int t = gi();
    return t--;
}

#define MD 1000000007
int mx[200004];
int mn[200004];

void upd(map<int, ll> &m, int k, ll v) {
    if (m.find(k) == m.end() || v < m[k])
        m[k] = v;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    I(n);
    F(i, n) {
        mn[i] = MD;
        mx[i] = -MD;
    }

    F(i, n) {
        I(x);
        I(c) - 1;
        mn[c] = min(mn[c], x);
        mx[c] = max(mx[c], x);
    }

    map<int, ll> m;
    m[0] = 0;
    F(i, n) if (mn[i] != MD) {
        map<int, ll> m2;
        for (auto &it : m) {
            upd(m2, mx[i], it.second + ABS(mn[i] - it.first) + mx[i] - mn[i]);
            if (mx[i] != mn[i])
                upd(m2, mn[i], it.second + ABS(mx[i] - it.first) + mx[i] - mn[i]);
        }
        m = m2;
    }

    ll res = 100000000000000000LL;
    for (auto &it : m)
        res = min(res, it.second + ABS(it.first));

    cout << res << endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define pb                    push_back
#define ll                    long long
#define ld                    long double
#define sz(x)                 (ll)x.size()
#define vll                   vector<long long>

#define infi                  INT_MAX
#define infl                  LONG_LONG_MAX
#define infd                  LDBL_MAX
#define f(i,a,b)              for(ll i=a;i<b;i++)
#define fi(i,a,b)             for(ll i=(b-1);i>=a;i--)
#define F                     first
#define S                     second
#define G(a,b)                get<a>(b)
#define MP                    make_pair
#define MT                    make_tuple
#define pll                   pair<ll,ll>
#define endl                  "\n"
#define ALL(v)                v.begin(),v.end()
#define nl                    cout<<"\n";
#define deb                   cout<<"***************************************************************************************\n";
#define moshi                 cout<<"moshi moshi ! \n";
#define hi                    cout<<"hi ! \n";
#define bye                   cout<<"bye bye ! \n";
#define kawai                 cout<<"O kawai koto ! \n";
#define o_set                 tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define number_of_set_bits  __builtin_popcountll
#define eb                    emplace_back
const ld PI=3.1415926535897932384626433;

template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T> >;


auto clk=clock();
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 <<"\n";
        //use cerr if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

//**********************************************************  Code begins  ***********************************************

// trick for traversing all submasks
// for (ll j=mask ;j; j=(j-1)&mask)  // also include 0 manually
// v.resize(unique(v.begin(), v.end()) - v.begin());    // remove duplicates

const ll N=1e5+5;
ll n,m,k,a[N],mn[N],mx[N],b[N];

ll ceil(ll p,ll q)
{
    ll res=(p+q-1)/q;
    return res;
}

bool can(ll d)
{
    ll small=0,big=0;
    f(i,1,k+1)
    {
        mn[i]=ceil(-d+a[i]*m,n);
        mx[i]=(d+a[i]*m)/n;
        small+=mn[i];
        big+=mx[i];
    }

    return (small<=m && big>=m);
}

void help(ll d)
{
    ll small=0,big=0,extra=m;
    f(i,1,k+1)
    {
        mn[i]=ceil(-d+a[i]*m,n);
        mx[i]=(d+a[i]*m)/n;
        small+=mn[i];
        big+=mx[i];
        extra-=mn[i];
    }

    f(i,1,k+1) 
    {
        ll give=mx[i]-mn[i],take=min(give,extra);
        extra-=take;
        b[i]=mn[i]+take;
    }
}

void solve()
{
    cin>>k>>n>>m;
    f(i,1,k+1) cin>>a[i];
    ll lef=0,rig=1e18,mid,res=-1;
    while(lef<=rig)
    {
        mid=(lef+rig)>>1;
        if(can(mid)) res=mid,rig=mid-1;
        else lef=mid+1;
    }
    help(res);
    f(i,1,k+1) cout<<b[i]<<" ";
    nl
}


int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout<<fixed<<setprecision(8);


    ll test_cases=1;
    //cin>>test_cases;

    f(i,1,test_cases+1)
    {
        solve();
        //clr();
    }


    #ifdef rd
    cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
    #endif

    return 0;
}
