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 alwa ys 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 n assignments due next week. The i th assignment takes x i units of time and must be finished by time ti . David can only work on one assignment at a time, and once David begins an assignment, he must work until it is finished. What is the latest time that David can start in order to ensure that all his deadlines are met?
입력 3 1 2 1 9 9 7 출력 5 입력 2 2 2 3 3 출력 impossible
출처:standford/2008/