CF671E Organizing a Race

Kekoland is a country with $ n $ beautiful cities numbered from left to right and connected by $ n-1 $ roads. The $ i $ -th road connects cities $ i $ and $ i+1 $ and length of this road is $ w_{i} $ kilometers. When you drive in Kekoland, each time you arrive in city $ i $ by car you immediately receive $ g_{i} $ liters of gas. There is no other way to get gas in Kekoland. You were hired by the Kekoland president Keko to organize the most beautiful race Kekoland has ever seen. Let race be between cities $ l $ and $ r $ ( $ l

The first line of the input contains two integers $ n $ and $ k $ ( $ 2

Print a single line — the beauty of the most beautiful race you can organize.

In first sample if you give one present to each city then it will be possible to make a race between city $ 1 $ and city $ 4 $ . In second sample you should add $ 1 $ to $ g_{5} $ and $ 4 $ to $ g_{6} $ , then it will be possible to make a race between cities $ 2 $ and $ 8 $ .