URI Online Judge | 2823

Eearliest Deadline First

By Emilio Wuerges, UFFS BR Brazil

Timelimit: 1

Your job for this problem is to check if it is possible to schedule a set of periodic tasks under real-time constraints.

A real-time task is defined by two numbers. The first number is the computational cost of the task. It is the computational cost of each complete run of the task. The second number is the period of the process. In other words, the process restarts again after each period.

The task set will be scheduled using the EDF algorithm (Earliest Deadline First). It is known that EDF is optimal. This means that if a set of tasks cannot be scheduled by EDF, there isn't another algorithm that can schedule it.

The operating system that will run these tasks runs on a single core machine. The tasks are preemptable. That is, a task can take the place of another task during its run, if required.

Consider that the cost of switching tasks is 0.


The first line of the input has a value  \(1 \leq N \leq 10\), which states the number of processes under schedule.

Every N following line represents a process, and has 2 values \(1 \leq C \leq 5\) and \(C \leq P \leq 100\), that represent the computational cost and the period of each process, respectively.


The output consists of a single line, with the string OK or the string FAIL, if the scheduling is possible or not, respectively.

Input Samples Output Samples

3 5
2 5


1 5
4 9
5 15
2 45