Dreadful Deadlines
Time limit1sMemory limit128 MB
Given n jobs with durations and deadlines, find the latest start time from which all jobs can still be finished by their deadlines.
Problem
Contrary to popular belief, diligence does not always pay off! Over the course of his years as an earnest Stanford undergraduate, David found that despite his best efforts, work would always expand to fill the time available. In order to improve his day-to-day efficiency, David has decided to learn the art of procrastination.
David has assignments due next week. The -th assignment takes units of time and must be finished by time . David can only work on one assignment at a time, and once he begins an assignment he must work on it until it is finished (he cannot switch away in the middle). What is the latest time at which David can start working so that all of his deadlines are still met?
Input
The input contains multiple test cases. Each test case consists of three lines. The first line contains a single integer (). The second line contains integers () separated by single spaces. The third line contains integers () separated by single spaces.
A blank line separates consecutive test cases. A single line containing marks the end of the input and must not be processed.
Output
For each test case, print on its own line a single integer: the latest time at which David can start and still finish all of his assignments on time. If this latest start time would be before time (that is, negative), print impossible instead.