#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct cvor
{
    char NAZIV_IGRACA[20];
    int PRIJAVLJENI_BROJ;
    struct cvor *l, *d;
} cvor;

int max( int x, int y )
{
    return x < y ? y : x;
}

//додавање новог елемента у претраживачко стабло
void dodaj( cvor **koren, char *ime, int x )
{
    if( !*koren )
    {
        *koren = ( cvor * ) malloc( sizeof( cvor ) );

        strcpy( ( *koren ) -> NAZIV_IGRACA, ime );
        ( *koren ) -> PRIJAVLJENI_BROJ = x;
        
        ( *koren ) -> l = NULL;
        ( *koren ) -> d = NULL;
    }
    else if( strcmp( ime, ( *koren ) -> NAZIV_IGRACA ) < 0 ) dodaj( &( *koren ) -> l, ime, x );
    else dodaj( &( *koren ) -> d, ime, x );
}

//испис стабла у корен-леви-десни формату
void ispis( cvor *koren )
{
    if ( !koren ) return;
    
    ispis( koren -> l );
    printf("%s %d\t", koren -> NAZIV_IGRACA, koren -> PRIJAVLJENI_BROJ );
    ispis( koren -> d );
}

//2Д приказ стабла
void razmak( char c, int n )
{
    while ( n -- ) putchar( c );
}

void vizuelniPrikaz( cvor *koren, int nivo )
{
    if ( !koren )
    {
        razmak('\t', nivo );
        puts("~");
    }
    else
    {
        vizuelniPrikaz( koren -> d, nivo + 1 );
        razmak('\t', nivo );
        printf("%s %d\n", koren -> NAZIV_IGRACA, koren -> PRIJAVLJENI_BROJ );
        vizuelniPrikaz( koren -> l, nivo + 1 );
    }
}


int maks( cvor *koren, int nivo )
{
    if( !koren ) return 0;
    if( !nivo ) return koren -> PRIJAVLJENI_BROJ;

    return max( maks( koren -> l, nivo -1), maks( koren -> d, nivo - 1 ) );
}


int main()
{
    cvor *koren = NULL;

    int n;
    scanf("%d", &n );getchar();

    while( n -- )
    {
        char ime[ 20 ];
        int br;
        scanf("%s %d", ime, &br );getchar();
        dodaj( &koren, ime, br );
    }

    ispis( koren ); putchar('\n');
    vizuelniPrikaz( koren, 0 );

    int nivo;
    scanf("%d", &nivo );

    printf("Maks na nivou %d je %d\n", nivo, maks( koren, nivo - 1 ) );
 
    return 0;
}