CF119C Education Reform

Yet another education system reform has been carried out in Berland recently. The innovations are as follows: An academic year now consists of $ n $ days. Each day pupils study exactly one of $ m $ subjects, besides, each subject is studied for no more than one day. After the lessons of the $ i $ -th subject pupils get the home task that contains no less than $ a_{i} $ and no more than $ b_{i} $ exercises. Besides, each subject has a special attribute, the complexity ( $ c_{i} $ ). A school can make its own timetable, considering the following conditions are satisfied: - the timetable should contain the subjects in the order of the complexity's strict increasing; - each day, except for the first one, the task should contain either $ k $ times more exercises, or more by $ k $ compared to the previous day (more formally: let's call the number of home task exercises in the $ i $ -th day as $ x_{i} $ , then for each $ i $ ( $ 1<i

N/A

N/A