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

int main(void) {

    char * line = NULL;
    size_t sz = 0;
    int line_count = -1;
    char buffer[100][100];
    int end_input = 0;

    while(end_input == 0) {
        ssize_t ln = getline(& line, & sz, stdin);

        if(ln > 0) {
            line_count += 1;
            sscanf(line,"%[^\n]%*c",buffer[line_count]);
        }

        if(atoi(buffer[(line_count)]) == 0) {
            end_input = 1;
        }

    }

    int i = 0;
    int j = 0;

    long weights[line_count];
    int element_counts[line_count];
    int first_space[line_count];
    int element_count = 0;
    int most_elements = 0;

    for(i=0;i<(line_count);i++) {
        for(j=0;j<strlen(buffer[i]);j++) {
            if(isspace(buffer[i][j]) == 0) {
                if(element_count < 2) {
                    first_space[i] = j;
                }
            }
            else {
                element_count += 1;
            }
        }
        element_counts[i] = element_count;
        if(element_count > most_elements) {
            most_elements = element_count;
        }
        element_count = 0;
    }

    char elements[line_count][most_elements];

    for(i=0;i<line_count;i++) {
        element_count = 0;
        for(j=(first_space[i]);j<strlen(buffer[i]);j++) {
            if(isspace(buffer[i][j]) == 0) {
                elements[i][element_count] = buffer[i][j];
                element_count += 1;
            }
        }
    }

    char universe[100];
    int k = 0;
    int u_count = 0;
    int matcher = 0;

    for(i=0;i<line_count;i++) {
        for(j=0;j<element_counts[i];j++) {
            if(u_count == 0) {
                universe[u_count] = elements[i][j];
                u_count += 1;
            }
            else {
                matcher = 0;
                for(k=0;k<strlen(universe);k++) {
                    if(universe[k] == elements[i][j]) {
                        matcher = 1;
                    }
                }
                if(matcher == 0) {
                    universe[u_count] = elements[i][j];
                    u_count += 1;
                }
            }
        }
    }

    //sort for alphabetical list
    char universe_sorted[100];
    char next_alpha[1];
    char last_alpha[1];

    next_alpha[0] = 'z';
    last_alpha[0] = 0;

    for(i=0;i<u_count;i++) {
        for(j=0;j<u_count;j++) {
            if(i==0 && universe[j]<=next_alpha[0]) {
                next_alpha[0] = universe[j];
            }
            else if((universe[j]<=next_alpha[0]) && (universe[j]>last_alpha[0])) {
                next_alpha[0] = universe[j];
            }
        }
        universe_sorted[i] = next_alpha[0];
        last_alpha[0] = next_alpha[0];
        next_alpha[0] = 'z';
    }

    //print universe to console
    for(i=0;i<u_count;i++) {
        if(i==0) {
            printf("\n\nUniverse: { %c",universe_sorted[i]);
        }
        else {
            printf(", %c",universe_sorted[i]);
        }
    }
    printf(" %s\n\n","}");

    char temp_buf[100];

    for(i=0;i<line_count;i++) {
        memcpy(temp_buf,buffer[i],first_space[i]);
        weights[i] = atol(temp_buf);
        printf("Set %i:\n",(i+1));
        printf("Weight = %ld\n",weights[i]);
        printf("Elements = { %c",elements[i][0]);
        for(j=1;j<element_counts[i];j++) {
            printf(", %c",elements[i][j]);
        }
        printf("%s\n\n"," }");
    }
    
    printf("\n%s\n\n","BEGIN STEPS:");

    long smallest_weight = 9999;
    int selected_line = 0;
    long chosen_values[strlen(universe_sorted)];
    int z = 0;
    long line_remainder[line_count];
    int decided[line_count];
    int chosen[strlen(universe_sorted)];
    int printed = 0;

    for(i=0;i<strlen(universe_sorted);i++) {
        chosen[i] = 0;
        chosen_values[i] = 0;
    }

    for(i=0;i<line_count;i++) {
        decided[i] = 0;
        line_remainder[i] = weights[i];
    }

    int current_step = 0;

    for(i=0;i<strlen(universe_sorted);i++) {
        if(chosen[i]==0) {
            current_step += 1;
            printf("Step %d:\n",current_step);
            for(j=0;j<line_count;j++) {
                if(line_remainder[j]>0) {
                    line_remainder[j] = weights[j];
                    printf("X%d = 0 or",(j+1));
                    printed = 0;
                    for(k=0;k<element_counts[j];k++) {
                        for(z=0;z<strlen(universe_sorted);z++) {
                            if(elements[j][k] == universe_sorted[z]) {
                                if(chosen[z]==1) {
                                    line_remainder[j] -= chosen_values[z];
                                }
                                else {
                                    if(printed==0) {
                                        printf(" Y%c ",elements[j][k]);
                                        printed = 1;
                                    }
                                    else {
                                        printf(" + Y%c ",elements[j][k]);
                                    }
                                }
                            }
                        }
                    }
                    if(decided[j]<element_counts[j]) {
                        if(line_remainder[j] <= 0) {
                            printf(" = %d\n",0);
                        }
                        else {
                            printf(" = %ld\n",line_remainder[j]);
                        }
                    }
                    else {
                        printf(" %s\n","----");
                    }
                }
            }

            smallest_weight = 9999;
            selected_line = 0;

            for(j=0;j<line_count;j++) {
                for(k=0;k<element_counts[j];k++) {
                    if(elements[j][k] == universe_sorted[i]) {
                        if(line_remainder[j]<smallest_weight) {
                            smallest_weight = line_remainder[j];
                            selected_line = j;
                        }
                    }
                }
            }

            chosen_values[i] = line_remainder[selected_line];
            chosen[i] = 1;
            line_remainder[selected_line] = 0;

            printf("\nY%c = ",universe_sorted[i]);
            printf("%ld. S' = {",chosen_values[i]);

            for(j=0;j<line_count;j++) {
                for(k=0;k<element_counts[j];k++) {
                    for(z=0;z<strlen(universe_sorted);z++) {
                        if(elements[j][k] == universe_sorted[z]) {
                            if(line_remainder[j]==0) {
                                chosen[z] = 1;
                            }
                        }
                    }
                }
            }

            for(j=0;j<line_count;j++) {
                decided[j] = 0;
                for(k=0;k<element_counts[j];k++) {
                    for(z=0;z<strlen(universe_sorted);z++) {
                        if(elements[j][k] == universe_sorted[z]) {
                            if(chosen[z]==1) {
                                decided[j] += 1;
                            }
                        }
                    }
                }
            }

            printed = 0;

            for(j=0;j<line_count;j++) {
                if(line_remainder[j]<=0) {
                    if(printed==0) {
                        printed=1;
                    }
                    else {
                        printf("%s",",");
                    }
                    printf(" s%d",(j+1));
                }
            }

            printf("%s"," }, C' = {");

            printed = 0;

            for(j=0;j<strlen(universe_sorted);j++) {
                if(chosen[j]==1) {
                    if(printed==0) {
                        printed=1;
                    }
                    else {
                        printf("%s",",");
                    }
                    printf(" %c",universe_sorted[j]);
                }
            }

            printf("%s\n\n\n"," }");
        }
    }

    long cost = 0;

    for(i=0;i<line_count;i++) {
        if(line_remainder[i]<=0) {
            cost += weights[i];
        }
    }

    printf("Cost = %ld\n",cost);

    return 1;
}