#define HOPERSO X
#define piccionemagico M,
#define sunnov8238pm priority_queue
#define nonsocosastofacendo pq.top
#define tungtungsteno mincammino
#define settantatrequarantadue 0
#define qualcunomistaguardando M
#define efs for
#define vfwcskljvkpwfsd vector
#define POV_DEI_BISCOTTI pair
#define chescemochesonoio if
#define toad long,
#define tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema u
#define luigi void
#define bfs Y
#define YAYYYYY w;
#define seisette &i:
#define scioccherellinooo i
#define catalan int
#define paperago ;
#define fragola !pq.empty
#define susssone ,
#define ohnoooo N
#define sus d
#define giaaaaaaaaaaaaaaaaa M;
#define googleChrome 0;
#define iorewivfj pq;
#define AFS_PROBLEMA_SEGRETO pq.pop
#define IPERSUSSONE 4
#define mario int,
#define blublurblablubbluss X,
#define cfs w
#define pikapikaCHUUUUUUCHUHCUSIDVJAO 1e18
#define CIAISSIMO N,
#define qwertyuiopasdfghjklzxcvbnm P
#define ifohncm std;
#define z G
#define papera P,
#define super_perdita D
#define treap_di_dsu namespace
#define camicie while
#define piccionebuco v
#define tastiera 1;
#define quaqua cin
#define gughel w,
#define ciao D.resize
#define biscottiniii .push_back
#define pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA u,
#define gnamgnam auto
#define hehehe d,
#define piccionebasta Y,
#define topolino main
#define scotch pq.emplace
#define sussizerello using
#define aria 0,
#define BASTAAAA long
#define we &
#define timmy_loves_gambling :
#include <bits/stdc++.h>
sussizerello treap_di_dsu ifohncm 
 
#define ll long long
#include <cassert>
 
luigi tungtungsteno(catalan CIAISSIMO catalan piccionemagico vfwcskljvkpwfsd<catalan> blublurblablubbluss vfwcskljvkpwfsd<catalan> piccionebasta vfwcskljvkpwfsd<catalan> papera vfwcskljvkpwfsd<BASTAAAA BASTAAAA>we super_perdita) { 
    sunnov8238pm<POV_DEI_BISCOTTI<BASTAAAA toad BASTAAAA BASTAAAA>> iorewivfj 
 
    vfwcskljvkpwfsd < vfwcskljvkpwfsd < POV_DEI_BISCOTTI<mario catalan> > > z ( ohnoooo )paperago 
    ciao(settantatrequarantadue)paperago 
 
    ciao(CIAISSIMO pikapikaCHUUUUUUCHUHCUSIDVJAO)paperago 
    super_perdita[settantatrequarantadue] = googleChrome 
 
    efs(catalan scioccherellinooo = googleChrome scioccherellinooo < ohnoooo-tastiera scioccherellinooo++) { 
        z[HOPERSO[scioccherellinooo]]biscottiniii({bfs[scioccherellinooo]susssone qwertyuiopasdfghjklzxcvbnm[scioccherellinooo]})paperago 
    } 
 
    scotch(aria settantatrequarantadue)paperago 
 
    camicie(fragola()) { 
        gnamgnam [hehehe piccionebuco] = nonsocosastofacendo()paperago 
        AFS_PROBLEMA_SEGRETO()paperago 
 
        efs(gnamgnam [pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA cfs]timmy_loves_gambling z[piccionebuco]) { 
            chescemochesonoio(super_perdita[tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema] > -sus + cfs) { 
                super_perdita[tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema] = - sus + YAYYYYY 
                scotch(sus - gughel tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema)paperago 
            } 
        } 
    } 
 
 
    efs(gnamgnam seisette super_perdita) chescemochesonoio(scioccherellinooo >= pikapikaCHUUUUUUCHUHCUSIDVJAO - IPERSUSSONE) scioccherellinooo = -tastiera 
 
} 
 
#ifndef EVAL
catalan topolino() { 
    catalan CIAISSIMO giaaaaaaaaaaaaaaaaa 
    quaqua >> ohnoooo >> giaaaaaaaaaaaaaaaaa 
 
    vfwcskljvkpwfsd<catalan> HOPERSO(qualcunomistaguardando)susssone bfs(qualcunomistaguardando)susssone qwertyuiopasdfghjklzxcvbnm(qualcunomistaguardando)paperago 
    vfwcskljvkpwfsd<BASTAAAA BASTAAAA> super_perdita(ohnoooo)paperago 
 
    efs (catalan scioccherellinooo = googleChrome scioccherellinooo < giaaaaaaaaaaaaaaaaa scioccherellinooo++) { 
        quaqua >> HOPERSO[scioccherellinooo] >> bfs[scioccherellinooo] >> qwertyuiopasdfghjklzxcvbnm[scioccherellinooo]paperago 
    } 
 
    tungtungsteno(CIAISSIMO piccionemagico blublurblablubbluss piccionebasta papera super_perdita)paperago 
} 
#endif