Редење коцки
Малата Радмила обожава да гради кули од коцки. Татко и сака истата да ги научи бројките, па затоа и смислил интересна игра. На почеток, во ред се поредуваат N мали коцки кои претставуваат кули со висина 1 (како на сликата). Потоа, тој и задава наредби од следниот тип:
„На сите кули од i-тата до ј-тата стави по една коцка.“
Или
„Од сите кули од i-тата до ј-тата извади по една коцка.“
Така, Радмила ќе научи да брои.
Сепак, за да не му е досадно, татко и нашол дополнителна занимација. Тој, во даден момент ги констатира висините на сите кули, избира целна ситуација (на висини на кулите) и и задава наредби на Радмила за да дојде до таа ситуација.
Ваша задача е за дадена почетна и целна ситуација, да пресметате со колку најмалку наредби може да се достигне истата.
Влез
Во првата линија има еден позитивен цел број N (1≤N ≤ 2000).
Во втората линија има N цели броеви Pi (0 ≤ Pi ≤ 99), кои ги означуваат висините на i-тата кула во почетната ситуација.
Во втората линија има N цели броеви Ki (0 ≤ Ki ≤ 99), кои ги означуваат висините на i-тата кула во целната ситуација.
Забелешка: Во тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 50.
Излез
Во единствената линија, се печати бројот кој се бара во описот на проблемот.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 3 3 4 5 7 8 9 | излез 4 |
влез 4 1 2 3 4 2 1 1 0 | излез 5 |
влез 4 5 4 5 5 0 5 1 2 | излез 10 |
Објаснување за вториот пример:Целната ситуација може да се достигне со најмалку 5 наредби. На пример со наредбите:
-На сите кули од 1-тата до 1-тата стави по една коцка.
-На сите кули од 2-тата до 4-тата извади по една коцка.
-На сите кули од 3-тата до 4-тата извади по една коцка.
-На сите кули од 4-тата до 4-тата извади по една коцка.
-На сите кули од 4-тата до 4-тата извади по една коцка.
ќе може да се достигне целната ситуација.