Description

某座大桥上有n1条从左至右的车道，n2(n1,n2≤10)

条从右至左的车道，还有一条潮汐车道。

在早上从左向右行驶的车辆较多，潮汐车道的方向是

从左向右；晚上正好相反。

也就是说早上有n1+1条左右车道，n2条右左车道；晚

上有n1条左右车道，n2+1条右左车道。

交通是很复杂的问题，我们有如下的抽象模型：

从早到晚被分为m(m≤100000)个离散的时刻，编号从1开始。

在每个时刻，两侧均有一些车抵达。

设左右车道和右左车道各有L,R条车道，那么左侧通行L辆车

（即减少L辆车），右侧通行R辆车。

剩下的车等待下一时刻。

如果在时刻m后仍有车辆在等待，那么后面的时刻仍按同样模

型进行，只是不会有新到达的车辆了。

你的任务是决定在哪一时刻改变潮汐车道的方向，能

使所有车辆等待时间的总和最小化。

不过潮汐车道也不是瞬间就能改变方向的，它需要r

个时刻来改变方向。也就是说，如果在t时刻改变方向，那么在[t,t+r-1]

时刻内潮汐车道不能使用，即左右和右左车道各有n1和n2条。

Format