Before an Exam · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Math

Greedy

Amazon

Before an Exam

Distribute a total study time across several days so each day receives a value within a given range, if possible.

Acceptance 0%

Start Practice

Problem Statement

You are given $n$ days before an exam. For each day $i$ , you know a minimum and maximum amount of time you can study on that day: from $a_i$ to $b_i$ hours inclusive.

Your task is to assign an integer number of study hours to every day so that:

the total sum of assigned hours is exactly $s$ ;
for every day $i$ , the assigned value lies in the interval $[a_i, b_i]$ .

If such an assignment exists, output one valid schedule. Otherwise, report that it is impossible.

A common way to think about the problem is to start with the minimum required time for every day, then distribute the remaining hours without exceeding the daily upper bounds.

Input Format

The first line contains two integers $n$ and $s$ .
The next $n$ lines each contain two integers $a_i$ and $b_i$ describing the allowed range for day $i$ .

Output Format

If no valid assignment exists, print NO.
Otherwise print YES on the first line, followed by one line with $n$ integers describing a valid assignment.

Constraints

$1 \le n$
All assigned values must be integers.
For each day $i$ , the chosen value must satisfy $a_i \le x_i \le b_i$ .
The total sum must equal $s$ .

Exact numeric bounds are not provided in the source metadata, but the intended solution is linear or near-linear in $n$ .

Examples

Sample cases returned by the problem API.

Example 1

Input

Output

YES
3 3 4

Explanation

The minimum total is 1+2+1=4, leaving 6 extra hours to distribute. One valid distribution is 3, 3, and 4, which sums to 10 and stays within all ranges.

Example 2

Input

2 1
2 3
1 2

Output

NO

Explanation

The minimum total is 2+1=3, which is already larger than the required sum 1.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress