Поликарп мечтает о покупке нового компьютера, который стоит \(c\) тугриков. Для этого он хочет устроиться программистом в большую компанию.
В компании Поликарпа есть \(n\) должностей, пронумерованных начиная с единицы. Сотрудник на должности \(i\) каждый день зарабатывает \(a[i]\) тугриков. Чем выше номер должности, тем больше тугриков получает сотрудник. Изначально Поликарп устраивается на должность с номером \(1\) и имеет \(0\) тугриков.
Каждый день Поликарп может сделать одно из двух действий:
- Если Поликарп находится на должности \(x\), то он может заработать \(a[x]\) тугриков;
- Если Поликарп находится на должности \(x\) (\(x < n\)) и имеет хотя бы \(b[x]\) тугриков, то он может потратить \(b[x]\) тугриков на онлайн-курс и перейти на должность \(x+1\).
Например, если \(n=4\), \(c=15\), \(a=[1, 3, 10, 11]\), \(b=[1, 2, 7]\), то Поликарп может действовать так:
- В первый день Поликарп находится на должности \(1\) и зарабатывает \(1\) тугрик. Теперь у него есть \(1\) тугрик;
- Во второй день Поликарп находится на должности \(1\) и переходит на должность \(2\). Теперь у него есть \(0\) тугриков;
- В третий день Поликарп находится на должности \(2\) и зарабатывает \(3\) тугрика. Теперь у него есть \(3\) тугрика;
- В четвертый день Поликарп находится на должности \(2\) и переходит на должность \(3\). Теперь у него есть \(1\) тугрик;
- В пятый день Поликарп находится на должности \(3\) и зарабатывает \(10\) тугриков. Теперь у него есть \(11\) тугриков;
- В шестой день Поликарп находится на должности \(3\) и зарабатывает \(10\) тугриков. Теперь у него есть \(21\) тугриков;
- Спустя шесть дней, Поликарп может купить себе новый компьютер.
Найдите минимальное количество дней, через которое Поликарп сможет купить себе новый компьютер.