Problem F
Wearing Jackets
You are not a big fan of temperature changes. You always prefer the temperature to be $70$ degrees Fahrenheit. Unfortunately, the temperature where you live is typically lower. To combat this, you purchased $K$ jackets that each individually increase your temperature by $T_i$. They don’t fit on you when you try wearing more than one at a time, and you don’t have enough room to carry any additional jackets throughout the day, so you can only bring up to $1$. At any time during the day, you can take off your jacket or wear the jacket you brought, if you brought one. You just checked the forecast for the next $D$ days and found the high and low temperatures, $L_j$ and $H_j$, for those days. For every integer temperature from $L_j$ to $H_j$, there will be a time when this is the current temperature. You want to keep the temperature you feel as close to $70$ degrees at all times.
Minimize the largest temperature difference from $70$ degrees you will feel each day by optimally choosing what jackets you’ll wear (if any).
Input
The first line of input contains $K$ and $D$, each integers between $1$ and $1\, 000$. The next $K$ lines each contain an integer with a temperature increase for one jacket. Line number $i$ will have the temperature increase $d_i$ for the $i^{\text{th}}$ jacket, which is an integer between $1$ and $70$ degrees Fahrenheit. The next $D$ lines after that will have the low and high temperatures for the day. These temperatures will be given in Fahrenheit and be integers between $0$ and $70$.
Output
On $D$ lines, output a nonnegative integer representing the optimal temperature difference for each day between day $1$ and day $D$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 1 3 5 63 68 66 70 |
2 1 |
