Авиакомпания <<Флагманский Флот Татарстана>> предлагает в своих самолётах новый вид бизнес-класса. Салон самолёта состоит из \(n\) мест, расположенных в один ряд вдоль прохода. Введём координатную прямую вдоль салона так, что расстояние между креслами будет равно \(1\), и места будут иметь координаты от \(1\) до \(n\).
Во время полёта стюарду нужно пройти по самолету и раздать всем пассажирам напитки. Напитки бывают \(k\) разных видов, пронумерованных числами от \(1\) до \(k\). Каждый пассажир получает одну порцию одного напитка, пассажир заказывает предпочитаемый вид напитков при бронировании билета, поэтому все предпочтения пассажиров известны заранее.
Напитки разлиты по бутылкам, каждая бутылка вмещает \(p\) порций одного напитка. В тележку для напитков можно загрузить не более \(m\) бутылок с любыми видами напитков, гарантируется, что \(m\ge k\).
Пассажиры обслуживаются в порядке возрастания номеров их мест. Первоначально тележка находится в начале салона в точке \(0\), и её можно заполнить любыми видами напитков перед обслуживанием. После завершения обслуживания тележка должна приехать в точку \(n+1\). При этом в точках \(0\) и \(n+1\) могут находиться кладовые: или одна кладовая в одном из концов салона или две кладовые в двух концах, в которых имеется достаточный запас напитков каждого вида. В этих кладовых можно выгрузить из тележки пустые бутылки и погрузить полные бутылки.
По ходу обслуживания напитки будут расходоваться, поэтому время от времени возникает необходимость пополнить запас напитков на тележке в одной из кладовых. Если в текущий момент тележка находится напротив кресла номер \(i\), то для того, чтобы доехать до кладовой в точке \(0\) необходимо проехать расстояние \(i\), а для того, чтобы доехать до кладовой в точке \(n + 1\) необходимо проехать расстояние \(n+1-i\). В кладовых можно выгрузить пустые бутылки из тележки и загрузить на свободные места бутылки с напитками любых видов. Выгружаемые бутылки должны быть пустыми, нельзя выгружать бутылки, в которых остались напитки, или выливать напитки. Нельзя переливать остатки напитков между разными бутылками. Можно загружать на тележку более одной бутылки одного вида. После этого тележка должна проехать расстояние от кладовой до кресла первого необслуженного пассажира, чтобы продолжить обслуживание.
Определите, какое минимальное расстояние должна проехать тележка, чтобы переместиться из точки \(0\) в точку \(n+1\) и обслужить всех пассажиров.
Формат входных данных
Первая строка входных данных содержит четыре целых числа \(n\), \(m\), \(k\), \(p\) (\(3 \leq n \leq 10^6\), \(1 \leq p \leq 10^6\), \(1 \leq k \leq m \leq 10^6\)) — количество мест в салоне, вместимость тележки, количество типов напитков и вместимость каждой бутылки соответственно.
В следующей строке содержится целое число \(c\) (\(1 \leq c \leq 3\)) — параметр, описывающий наличие кладовых в салоне. Если \(c=1\), то кладовая находится только в точке \(n+1\). Если \(c=2\), то кладовая находится только в точке \(0\). Если \(c=3\), то кладовые находятся в обоих концах салона.
В следующей строке содержатся \(n\) целых чисел \(a_i\) (\(1 \leq a_i \leq k\)) — типы напитков, которые заказали пассажиры.
Формат выходных данных
Программа должна вывести одно целое число — минимальное расстояние, которое должна проехать тележка.
Пояснения к примерам
В первом примере в тележку вмещается \(m=2\) бутылки по \(p=1\) порции в каждой. Кладовая находится в конце салона. Первоначально тележку нужно загрузить бутылками с напитками вида \(1\) и \(2\), которые будут налиты пассажирам на местах \(1\) и \(2\), тележка проедет расстояние \(2\) от точки \(0\) до точки \(2\). После этого тележке нужно будет проехать до кладовой в конце салона (расстояние \(4\)), загрузить тележку бутылками вида \(1\) и \(2\) и вернуться к креслу номер \(3\) (тележка проедет расстояние \(3\)). Пассажирам на местах \(3\) и \(4\) выдаются напитки вида \(1\) и \(2\) (тележка проезжает расстояние \(1\) от места \(3\) до места \(4\)). После этого тележке понадобится ещё раз съездить в кладовую (от кресла \(4\) до кладовой расстояние \(2\)), вернуться из кладовой до кресла \(5\) (расстояние \(1\)), и проехать ещё \(1\) до конца салона. Общее расстояние равно \(2+4+3+1+2+1+1=14\).
Во втором примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой. Кладовая находится в начале салона. Необходимо загрузить тележку тремя бутылками вида \(1\), обслужить пассажиров на местах с номерами от \(1\) до \(4\). После этого опустошатся две бутылки вида \(1\), нужно будет сразу съездить в кладовую, чтобы загрузить две бутылки вида \(2\), затем обслужить пассажиров на местах с номерами от \(5\) до \(8\).
В третьем примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой, кладовые находятся в обоих концах салона. Для обслуживания пассажиров нужны две бутылки вида \(2\) и по одной бутылке видов \(1\) и \(3\), поэтому понадобится один раз съездить в кладовую для того, чтобы заменить пустую бутылку вида \(2\) на полную. Это лучше сделать после обслуживания пассажира на месте \(3\), тележка должна съездить в кладовую в начале салона.
В четвёртом примере в тележку нужно загрузить по одной бутылке каждого вида, и поскольку каждая бутылка вмещает по две порции напитков, это позволит обслужить всех пассажиров без дополнительного пополнения тележки.
В пятом примере понадобится два пополнения тележки, один раз тележке придётся вернуться в кладовую в начало салона после обслуживания пассажира \(3\), второй раз — в конец салона после обслуживания пассажира \(6\).