Студент Вася приехал учиться в Берляндский государственный университет из деревни, поэтому живет в общежитии. Семестр длится n дней, и в каждый из этих дней родители присылают ему еды. Утром i-го дня ему приходит a_i килограмм еды, которую можно есть как в текущий, так и на следующий день (затем еда портится и становится непригодной к употреблению).

Каждый день Вася съедает v килограмм еды. Известно, что родители Васи не допустят, чтобы он голодал, поэтому еды Васе хватает всегда. У Васи есть m друзей, которые иногда у него живут. Пусть друзья пронумерованы числами от 1 до m. Друг с номером j живет у Васи со дня номер l_j по день номер r_j включительно. Также j-му другу в день необходимо съесть f_j килограмм еды. Обычно друзья Васи питаются в столовой, но иногда щедрый Вася кормит некоторых из них. Каждый день Вася может покормить каких-то друзей, которые живут у него в этот день (а может и не кормить никого).

Каждый раз, когда Вася угощает друга, он дает ему ровно столько еды, сколько необходимо другу в день, и Васин рейтинг популярности в университете повышается на единицу. Вася не может угощать одного и того же друга несколько раз в течение одного дня. Кроме того, он прекрасно знает, что режим питания нарушать нельзя, и поэтому он обязательно должен съедать в день v килограмм еды.

Вася хочет таким образом выбирать, кого он будет кормить в каждый из дней в семестре, чтобы его рейтинг стал как можно больше. Изначально рейтинг Васи равен 0, потому что он первокурсник.