На ферме UCPC в ряд вбиты $N$ кольев. Эти колья вбиты на случайную высоту, поэтому они выглядят некрасиво. Поэтому вам нужно отрегулировать высоту кольев, чтобы ферма UCPC выглядела красиво.

Каждый кол пронумерован слева направо от $1$ до $N$, и начальная высота $i$-го кола составляет $H_i$ см. Кроме того, поскольку материалы каждого кола различаются, сила, необходимая для того, чтобы поднять или вбить каждый кол, также различается. Чтобы поднять $i$-й кол на $1$ см, требуется сила $A_i$, а чтобы вбить его на $1$ см глубже, требуется сила $B_i$.

Красота фермы UCPC определяется длиной самого длинного непрерывного подотрезка кольев, имеющих одинаковую высоту. Найдем минимальную силу, необходимую для того, чтобы сделать красоту фермы UCPC не менее $K$.

Рисунок E.1: Начальное состояние кольев с красотой 1

Рисунок E.2: Увеличение красоты до 3 путем приложения силы

Входные данные

В первой строке задаются количество кольев $N$ и требуемая красота фермы UCPC $K$ ($1 \le N \le 100\,000$, $1 \le K \le N$).

В следующей строке через пробел задаются начальные высоты каждого кола $H_1, H_2, \dots, H_N$ ($1 \le H_i \le 100\,000$, $1 \le i \le N$).

В следующей строке через пробел задаются значения силы $A_1, A_2, \dots, A_N$, необходимые для поднятия каждого кола на $1$ см ($1 \le A_i \le 20\,000$, $1 \le i \le N$).

В следующей строке через пробел задаются значения силы $B_1, B_2, \dots, B_N$, необходимые для вбивания каждого кола на $1$ см ($1 \le B_i \le 20\,000$, $1 \le i \le N$).

Все входные значения являются целыми числами.

Выходные данные

Выведите минимальную силу, необходимую для того, чтобы сделать красоту фермы UCPC не менее $K$.

Примеры

Входные данные 1

2 2
1 3
4 1
1 3

Выходные данные 1

6

Входные данные 2

5 3
1 2 3 2 1
1 3 1 3 4
1 3 5 3 1

Выходные данные 2

5