P3537 [POI 2012] SZA-Cloakroom

The annual rich citizen's reunion is taking place in Byteotia. They meet to boast about their incomes, Lebytene's shoes and other luxuries. Naturally, not all these objects of pride are carried into the banquet - coats, jackets, umbrellas and such are left in the cloakroom, and picked up upon leave. Unfortunately for the well off, a gang of Byteotian thieves plans to break into the cloakroom and steal part of the items stored therein. At this very moment the gang's leader is examining the plans of the robbery put forward by other gang members (they are a democratic lot!). A plan typically looks as follows: the thieves break into the cloakroom at time $m_j$, take items worth exactly $k_j$ and escape, where the whole heist takes them $s_j$ time. The gang leader would first of all like to know which of these plans are feasible and which are not. A plan is feasible if at time $m_j$ it is possible to collect items of total value $k_j$ in such a way that up to the very $m_j+s_j$ moment no one shows up to retrieve any of the stolen goods (in such event, they would notify security, and the robbery would fail). In particular, if at time $m_j$ it is impossible to select items of exact total worth $k_j$, then the plan is infeasible and consequently rejected. Knowing the drop off and retrieval times for each item, determine which plans are feasible and which are not. We assume that an item left in the cloakroom the moment a robbery starts can already be stolen (see the example).

无

无