#include <stdio.h>

#define JOB (5)
#define PERSON (5)
#define DEFAULTMIN (35*PERSON)
int
    table[JOB][PERSON]={
        {10,  5,  7, 12,  8},
        {14, 20, 15, 10, 15},
        {18, 30, 20, 25, 22},
        {35,  8, 18, 20, 12},
        {20, 13,  8, 10, 17},
    };

static int nextplaces(int *place, int len, int max){
    //add most left place
    int
        i,
        flags;
    
    //loop while "place" is containg the same number in.
    for(;;){
        //next "place"
        for(i=0;i<len;i++){
            if((place[i]=(place[i]+1)%max)!=0)
                break;
        }
        
        //if place is maximum number((max-1)^len), then it returns 1;
        if(i==len)
            return 1;
        else{
            //else check "place" hasn't a same number in.
            for(i=flags=0;i<len;i++){
                if(flags & (2<<place[i])){
                    flags=0;
                    break;
                }else
                    flags|=2<<place[i];
            }
            if(flags)
                return 0;
        }
    }
}

int main(void){
    int
        person,
        job,
        min,
        place[PERSON], mem[PERSON];
    
    //clear "place"
    for(job=0;job<JOB;place[job++]=0);
    
    //compute minimum number
    min=DEFAULTMIN;
    for(;!nextplaces(place, PERSON, JOB);){
        int sum;
        sum=0;
        //get sum
        for(person=0;person<PERSON;person++)
            sum+=table[place[person]][person];
        
        //compare
        if(min>sum){
            //replace place
            for(person=0;person<PERSON;person++)
                mem[person]=place[person];
            min=sum;
        }
    }
    
    //outputs
    printf("minimum is %d\n", min);
    for(person=0;person<PERSON;person++)
        printf("person%d does job%d(cost %d)\n", person, mem[person], table[mem[person]][person]);
    
}