#include <stdio.h>

#define MAX 10

int main() {
    int n, r;
    printf("Enter number of processes: ");
    scanf("%d", &n);
    printf("Enter number of resources: ");
    scanf("%d", &r);

    int alloc[MAX][MAX], max[MAX][MAX], need[MAX][MAX];
    int avail[MAX], finish[MAX] = {0};
    int safeSeq[MAX];

    printf("Enter Allocation matrix:\n");
    for (int i = 0; i < n; i++)
        for (int j = 0; j < r; j++)
            scanf("%d", &alloc[i][j]);

    printf("Enter Max matrix:\n");
    for (int i = 0; i < n; i++)
        for (int j = 0; j < r; j++)
            scanf("%d", &max[i][j]);

    printf("Enter Available resources:\n");
    for (int j = 0; j < r; j++)
        scanf("%d", &avail[j]);


    for (int i = 0; i < n; i++)
        for (int j = 0; j < r; j++)
            need[i][j] = max[i][j] - alloc[i][j];

    
    int count = 0;
    while (count < n) {
        int found = 0;
        for (int i = 0; i < n; i++) {
            if (finish[i]) continue;

    
            int ok = 1;
            for (int j = 0; j < r; j++) {
                if (need[i][j] > avail[j]) {
                    ok = 0;
                    break;
                }
            }

            if (ok) {
        
                for (int j = 0; j < r; j++)
                    avail[j] += alloc[i][j];
                finish[i] = 1;
                safeSeq[count++] = i;
                found = 1;
            }
        }

        if (!found) break;  
    }

    if (count == n) {
        printf("\nSystem is in SAFE state\n");
        printf("Safe sequence: ");
        for (int i = 0; i < n; i++)
            printf("P%d ", safeSeq[i]);
        printf("\n");
    } else {
        printf("\nSystem is in UNSAFE state (Deadlock possible)\n");
    }

    return 0;
}