Слышали ли вы когда-нибудь о мессенджере QQ? В групповых чатах QQ администратор может заглушить пользователя на несколько дней.
В групповом чате Boboniu, есть человек, которого зовут Du Yi, который любит подшучивать над Boboniu каждый день.
Du будет общаться в чате на протяжении \(n\) дней. В \(i\)-й день:
- Если Du может разговаривать, он подшутит над Boboniu с фактором веселья \(a_i\). Но, после этого, он может быть заглушен, в зависимости от настроения Boboniu.
- Иначе, Du не будет ничего делать.
Настроение Boboniu это константа \(m\). В \(i\)-й день:
- Если Du может разговаривать и \(a_i>m\), тогда Boboniu разозлится и заглушит его на \(d\) дней, это означает, что Du не сможет говорить в дни \(i+1, i+2, \cdots, \min(i+d,n)\).
- Иначе, Boboniu не будет ничего делать.
Итоговой фактор веселья это сумма факторов веселья в дни, когда Du мог разговаривать.
Du попросил вас найти наибольший возможный фактор веселья по всем перестановкам \(a\).
Выходные данные
Выведите одно целое число: максимальный итоговый фактор веселья по всем перестановкам \(a\).
Примечание
В первом примере, вы можете переставить \(a'=[15, 5, 8, 10, 23]\). Тогда история общения Du будет выглядеть следующим образом:
- Подшутить над Boboniu с фактором веселья \(15\).
- Быть заглушенным.
- Быть заглушенным.
- Подшутить над Boboniu с фактором веселья \(10\).
- Подшутить над Boboniu с фактором веселья \(23\).
Таким образом, итоговый фактор веселья равен \(48\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 11
8 10 15 23 5
|
48
|
|
2
|
20 2 16
20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7
|
195
|