#include <stdio.h>

#define MAX 20

int main() {
    int n, m;
    int allocation[MAX][MAX], maximum[MAX][MAX], need[MAX][MAX];
    int available[MAX], work[MAX], finish[MAX], safeSeq[MAX];
    int i, j, k, count = 0;

    printf("Number of Processes: ");
    scanf("%d", &n);

    printf("Number of Resources: ");
    scanf("%d", &m);

    printf("\nAllocation Matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &allocation[i][j]);
        }
    }

    printf("\nMaximum Matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &maximum[i][j]);
        }
    }

    printf("\nAvailable Resources:\n");
    for (j = 0; j < m; j++) {
        scanf("%d", &available[j]);
    }

    /* Calculate Need Matrix */
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            need[i][j] = maximum[i][j] - allocation[i][j];

            if (need[i][j] < 0) {
                printf("\nInvalid Input! Allocation cannot be greater than Maximum.\n");
                return 0;
            }
        }
    }

    printf("\nNeed Matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            printf("%d ", need[i][j]);
        }
        printf("\n");
    }

    /* Initialize Work and Finish */
    for (j = 0; j < m; j++) {
        work[j] = available[j];
    }

    for (i = 0; i < n; i++) {
        finish[i] = 0;
    }

    /* Banker's Algorithm */
    while (count < n) {
        int found = 0;

        for (i = 0; i < n; i++) {
            if (finish[i] == 0) {
                int canExecute = 1;

                for (j = 0; j < m; j++) {
                    if (need[i][j] > work[j]) {
                        canExecute = 0;
                        break;
                    }
                }

                if (canExecute == 1) {
                    for (k = 0; k < m; k++) {
                        work[k] += allocation[i][k];
                    }

                    safeSeq[count] = i;
                    count++;
                    finish[i] = 1;
                    found = 1;
                }
            }
        }

        if (found == 0) {
            break;
        }
    }

    if (count == n) {
        printf("\nSystem is in SAFE STATE.\n");
        printf("Safe Sequence: ");

        for (i = 0; i < n; i++) {
            printf("P%d", safeSeq[i]);

            if (i != n - 1) {
                printf(" -> ");
            }
        }
        printf("\n");
    } else {
        printf("\nSystem is in UNSAFE STATE.\n");
        printf("No safe sequence exists.\n");
    }

    return 0;
}