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

//definindo uma cidade

typedef struct cidade {
    char nome[500];
    char estado[500];
    double valor;
} cidade;

//definindo um array_list

typedef struct array_list {
    int qtde;
    int cap;
    //vetor de ponteiros para cidades
    cidade ** cidades;

} array_list;

//verifica se array_list estÃ¡ cheio

int esta_cheio(array_list * l) {
    return l->qtde >= l->cap;
}
//dobra a capacidade do array_list, se necessÃ¡rio

void dobra_capacidade(array_list * l) {
    cidade ** aux = malloc(sizeof (cidade*) * (l->cap * 2));
    int i;
    for (i = 0; i < l->cap; i++) {
        aux[i] = l->cidades[i];
    }
    free(l->cidades);
    l->cidades = aux;
    l->cap *= 2;
}
//inicializa array_list
//adiciona no array_list

void add(array_list * l, char nome_cidade[], char estado[], double valor) {
    if (esta_cheio(l))
        dobra_capacidade(l);
    cidade * c = malloc(sizeof (cidade));
    strcpy(c->nome, nome_cidade);
    strcpy(c->estado, estado);
    c->valor = valor;
    l->cidades[l->qtde] = c;
    l->qtde = l->qtde + 1;
}

//obtem um array_list zerado com 4 de capacidade, inicialmente

array_list * obtem_array_list() {
    array_list * aux = malloc(sizeof (array_list));
    aux->cap = 4;
    aux->qtde = 0;
    aux->cidades = malloc(sizeof (cidade*) * aux->cap);
    return aux;
}

//exibe uma cidade

void exibe_cidade(cidade * c) {
    printf("%s %s %d\n", c->nome, c->estado, (int) c->valor);
}
//exibe um array_list

void exibe_array_list(array_list * l, int qtde) {
    int i;
    for (i = 0; i < l->qtde && i < qtde; i++) {
        exibe_cidade(l->cidades[i]);
    }
}

//funÃ§Ã£o que especifica criterio de comparaÃ§Ã£o entre duas cidades

int compara(const void * c1, const void * c2) {
    cidade ** aux1 = ((cidade**) c1);
    cidade ** aux2 = ((cidade**) c2);
    if ((*aux1)->valor < (*aux2)->valor)
        return 1;
    if ((*aux1)->valor == (*aux2)->valor)
        return 0;
    return -1;
}

//funcao que ordena um array_list de cidades

void ordena(array_list * l) {
    qsort((l->cidades), l->qtde, sizeof (cidade*), compara);
}

//cria cidade

cidade * cria_cidade(char * nome, char * estado, double valor) {
    cidade * c1 = malloc(sizeof (cidade));
    strcpy(c1->estado, estado);
    strcpy(c1->nome, nome);
    c1->valor = valor;
    return c1;
}
//teste adicao e ordenacao de cidades

void teste_add_sort_cidades() {
    printf("comecando...\n");
    array_list * cidades = obtem_array_list();
    add(cidades, "Sao Paulo", "SP", 1000);
    add(cidades, "Itapevi", "SP", 10000000);
    add(cidades, "Barueri", "SP", 200);
    exibe_array_list(cidades, cidades->qtde);
    ordena(cidades);
    exibe_array_list(cidades, cidades->qtde);
    printf("Terminando...");
}

void encontra_e_atualiza_ou_adiciona(array_list * l, char nome_cidade [], char estado[], double valor) {
    int i;
    for (i = 0; i < l->qtde; i++) {
        if (strcmp(l->cidades[i]->nome, nome_cidade) == 0 && strcmp(l->cidades[i]->estado, estado) == 0) {
            l->cidades[i]->valor += valor;
            return;
        }
    }
    add(l, nome_cidade, estado, valor);
}

int main() {
    //teste_add_sort_cidades();
    char entrada[100000];
    array_list * cidades = obtem_array_list();
    while (1) {
        fgets(entrada, 100000, stdin);
        entrada[strlen(entrada) - 1] = '\0';
        printf("%s\n", entrada);
        if (strcmp(entrada, "0") == 0)
            break;
        char * aux_split = strtok(entrada, ";");
        int cont = 0;
        char nome_cidade[500];
        char estado [500];
        double valor;
        int num_ganhadores;

        while (aux_split != NULL) {
            //printf("%s\n", aux_split);
            aux_split = strtok(NULL, ";");
            cont++;
            if (cont == 2) {
                num_ganhadores = atoi(aux_split);
            } else if (cont == 3) {
                strcpy(nome_cidade, aux_split);
            } else if (cont == 4) {
                strcpy(estado, aux_split);
            } else if (cont == 5) {
                valor = atof(aux_split);
                encontra_e_atualiza_ou_adiciona(cidades, nome_cidade, estado, valor * num_ganhadores);
                //add (cidades, nome_cidade, estado, valor);
                //exibe_array_list(cidades);
            }
        }
    }
    ordena(cidades);
    exibe_array_list(cidades, 3);
    return 0;
}
