The downstream API takes a request of at most budget bytes. Rows have to go out in order, packed into as few requests as possible.

Input

• rows — a list of (row_id, size_bytes), in the order they must be sent
• budget — int, the most a single batch may carry

Output

A list of (batch_index, row_id) — the batch each row was placed in, numbered from 0 in the order batches are opened. Order is not graded.

Example

Constraints

• Rows keep their order. This is packing, not sorting — reordering to fill a batch better would reorder the data downstream.
• A batch may reach the budget exactly. Closing it at that point costs a whole extra request every time the arithmetic is round.
• A row larger than the budget cannot be made to fit. It goes out on its own, and does not drag the row after it over the limit.