Сіз \(n\) деңгейден тұратын ойынды өтіп жатырсыз. Әр деңгейдің өзіндік құндылығы \(b_i\) бар — ол оң немесе теріс болуы мүмкін. Деңгейден өткен сайын сіз осы құндылықты аласыз.

Ойын процесі келесі түрде жүреді:

• әр деңгейде \(i\) сіз келесі деңгейге \(i+1\) өте аласыз,

• немесе алға секіру жасап, \(1\)-ден \(a_i\) аралығындағы кез келген деңгейге өте аласыз (яғни \(i + j\), мұндағы \(1 <= j <= a_i\)).

Алайда мұндай секіру — шектеулі ресурс, сондықтан сіз бүкіл ойын барысында \(k\) реттен артық секіре алмайсыз.

Ойын \(n+1\) деңгейіне жеткенде аяқталады. Сіздің мақсатыңыз — секіру мүмкіндігін тиімді пайдалана отырып, алынатын ұпайдың жалпы сомасын максималды ету.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(k\) — деңгей саны және рұқсат етілген секіру саны \((1 <= n, k <= 2000)\).

Екінші жолда \(n\) бүтін сан: \(a_1, a_2, \dots, a_n\) — әр деңгейден мүмкін болатын секіру ұзындықтары \((1 <= a_i <= n)\).

Үшінші жолда \(n\) бүтін сан: \(b_1, b_2, \dots, b_n\) — деңгейлердің құндылықтары \((-10^9 <= b_i <= 10^9)\).

Шығару

Бір бүтін сан — ойынды аяқтаған кезде алуға болатын максималды құндылық.

Мысалдар

Енгізу 1

5 2
3 2 4 1 2
10 -5 7 3 5

Жауап 1

25

Енгізу 2

4 1
2 1 1 1
5 6 7 8

Жауап 2

26

Енгізу 3

6 3
6 6 6 6 6 6
-10 -20 -30 5 6 7

Жауап 3

8

Ескертпелер

1-мысалға түсініктеме:

• \(1\) деңгейде — \(2\) деңгей алға секіреміз, \(3\) деңгейге өтіп, \(10\) ұпай аламыз.

• \(3\), \(4\), \(5\) деңгейлерінен жай өтеміз: сәйкесінше \(7\), \(3\) және \(5\) ұпай.

• Жалпы ұпай: \(10 + 7 + 3 + 5 = 25\). Бұл — ең жақсы нәтиже.

2-мысалға түсініктеме:

• Барлық деңгейлерде ұпайлар оң, сондықтан секіру жасаудың қажеті жоқ.

• Барлық деңгейлерден кезекпен өткен дұрыс: \(5 + 6 + 7 + 8 = 26\).

3-мысалға түсініктеме:

• \(1\) деңгейден бірден \(4\) деңгейге секіреміз (1 секіру жұмсалды).

• \(4\), \(5\), \(6\) деңгейлерінен жай өтеміз: \(5 + 6 + 7 = 18\) ұпай.

• Ал \(1\) деңгейдегі \(-10\) ұпайды ескерсек: \(-10 + 18 = 8\) ұпай.