Taco Running Schedule

You are given a running schedule problem where Peter wants to run a specified total distance over n days. For each day, there is a given minimum and maximum limit on the distance that can be run. The task is to determine whether it is possible to design a daily running schedule such that:

$$\sum_{i=1}^{n} d_i = D$$

and for each day \(i\), the distance \(d_i\) satisfies:

$$L_i \le d_i \le U_i$$

If it is possible, output "ACHIEVABLE" followed by one valid assignment of distances for each day; otherwise, output "NOT ACHIEVABLE". This problem requires balancing the extra distance beyond the minimum daily limits while respecting the maximum bounds.

Note: All formulas are presented in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(D\) where:

• \(n\) (1 \(\le\) n \(\le\) 10⁵) is the number of days.
• \(D\) (0 \(\le\) D \(\le\) 10⁹) is the total distance Peter wants to run.

The next \(n\) lines each contain two integers \(L_i\) and \(U_i\) (0 \(\le\) L_i \(\le\) U_i \(\le\) 10⁹), representing the minimum and maximum distance that can be run on day \(i\), respectively.

outputFormat

If a valid schedule exists, output "ACHIEVABLE" on the first line, and on the second line output \(n\) integers representing the distances for each day separated by spaces. If no valid schedule exists, output "NOT ACHIEVABLE".

## sample

1 20
5 10

NOT ACHIEVABLE