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