Vasya的电话里有n张照片。1号照片目前在手机上打开。通过在屏幕上滑动手指，可以向左和向右移动到相邻的照片。如果你从第一张照片向左滑动，你就会到达第n张照片。同样，从最后一张照片向右滑动，你会到达第1张照片。
对于每张照片，我们都知道它的方向是什么--水平或垂直。手机是垂直方向的，不能旋转。改变照片的方向需要b秒。
Vasya有T秒的时间看照片。他想尽可能多地观看照片。如果Vasya第一次打开照片，他要花1秒钟来注意照片的所有细节。如果照片的方向不对，他要花b秒时间旋转照片再看。如果Vasya已经打开了照片，他就跳过它（所以他不花任何时间来观察它或改变它的方向）。不允许跳过未看过的照片。
帮助Vasya找到他在T秒内能够观看的最大数量的照片。
Vasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.
For each photo it is known which orientation is intended for it − horizontal or vertical. Phone is in the vertical orientation and can't be rotated. It takes b second to change orientation of the photo.
Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn't spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.
Help Vasya find the maximum number of photos he is able to watch during T seconds.
Output
Output the only integer, the maximum number of photos Vasya is able to watch during those
T seconds.
Note
In the first sample test you can rotate the first photo (3 seconds), watch the first photo (1 seconds), move left (2 second), rotate fourth photo (3 seconds), watch fourth photo (1 second). The whole process takes exactly 10 seconds.
Note that in the last sample test the time is not enough even to watch the first photo, also you can't skip it.