Бизнесмен по имени Divan обожает шоколад! Сегодня он пришёл в магазин, чтобы закупиться им. Как и любой другой бизнесмен, Divan знает цену деньгам, поэтому он считает, что покупать слишком дорогие плитки шоколада не имеет никакого смысла, несмотря на всю его любовь к шоколаду. С другой же стороны, слишком дешёвый шоколад обычно слишком невкусный и вообще непонятно, зачем его покупать, ведь кроме отвращения он ничего не вызывает.
В магазине, в который он пришёл, есть \(n\) различных плиток шоколада, \(i\)-я из которых имеет цену \(a_i\) долларов. Слишком дорогой плиткой шоколада Divan считает такую, что её цена строго выше \(r\) долларов. Слишком дешёвой плиткой шоколада он считает такую, что её цена строго меньше, чем \(l\) долларов. Диван не будет покупать плитку, если она слишком дешёвая или слишком дорогая.
Кроме того, даже если по отдельности плитки шоколада не столь уж и дорогие, Divan, конечно, не собирается всю свою прибыль тратить на них, поэтому он ограничивает свои траты на шоколад \(k\) долларами.
Ваша задача заключается в том, чтобы определить, какое максимальное число плиток шоколада Divan сможет сегодня купить.
Выходные данные
Для каждого набора входных данных выведите единственное число — максимальное количество плиток шоколада, которые Divan сможет купить.
Примечание
В первом примере Divan сможет купить плитки шоколада под номерами \(1\) и \(3\) и потратит на это \(100\) долларов.
Во втором примере Divan сможет купить плитки шоколада под номерами \(3\) и \(4\) и потратит на это \(7\) долларов.
Во третьем примере Divan сможет купить плитки шоколада под номерами \(3\), \(4\) и \(5\), потратив на это \(12\) долларов.
В четвёртом примере Divan не может купить ни одной плитки шоколада, потому что каждую из них он считает либо слишком дешёвой, либо слишком дорогой.
В пятом примере Divan не может купить ни одной плитки шоколада, потому что первую плитку он считает слишком дешёвой, а на вторую и третью ему не хватит выделенного бюджета.
В шестом примере Divan сможет купить все плитки шоколада, которые есть в магазине.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 1 100 100
50 100 50
6 3 5 10
1 2 3 4 5 6
6 3 5 21
1 2 3 4 5 6
10 50 69 100
20 30 40 77 1 1 12 4 70 10000
3 50 80 30
20 60 70
10 2 7 100
2 2 2 2 2 7 7 7 7 7
4 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 1 1 1
1
|
2
2
3
0
0
10
1
1
|