In light of the approaching ICPC competition, you have made the decision to revamp your training plan. Recognizing the significance of maintaining both mental and physical stamina, you have allocated a specific number of days, denoted as n, from the remaining n + m days for intensive training. The remaining m days will be dedicated to rest and recovery. The primary objective is to strategize the distribution of training and rest days in a manner that maximizes your ICPC power.

During the training days, you can experience a boost in power, and consecutive training days yield even more substantial results. The power gain from training on the k-th day of consecutive training sessions follows a pattern of 2k - 1, where k = 1 signifies the first day of the training sequence. A single day of training contributes a power increase of 1, while two consecutive training days result in a power boost of 1 + 3 = 4, and three consecutive training days elevate the power by 1 + 3 + 5 = 9.

On the flip side, rest days lead to a reduction in power, and consecutive rest days accelerate this decline. Each day of rest within a sequence of k consecutive rest days diminishes the power by a value of 2k − 1, with k = 1 representing the initial day of the rest sequence. A single day of rest leads to a power reduction of 1, while two consecutive rest days cause a decline of 1 + 3 = 4, and three consecutive rest days result in a reduction of 1 + 3 + 5 = 9.

To maximize the overall increase in your ICPC power over the course of n + m days, it is crucial to devise an optimal training schedule. However, it is important to note that allocating an excessive number of rest days could potentially yield a negative power gain.

n and m are the numbers of training and repose days, respectively. Neither of them exceeds 10^6, and at least one of them is non-zero.

The end of the input is indicated by a line containing two zeros. The number of datasets does not exceed 100.

For each of the datasets, output in a line the largest increment of ICPC power after n + m days of training and repose by the best training schedule.

Dữ liệu vào Sao chép |

1 1 3 2 6 1 1 6 0 3 2 4 7 9 0 0 |

Dữ liệu ra Sao chép |

0 7 35 -17 -9 -4 10 |

Đăng nhập để làm bài