Бяцхан R "Дэд мөрийг устгах" нэртэй тоглоом тоглож байна. Энэ тоглоомонд $w$ бүхэл тоонуудаас бүрдсэн дараалал өгөгдсөн ба та дарааллыг өөрчилж оноо авч чадна. Өөрчлөлт нь ганцхан төрөл бөгөөд зөвхөн тэмдэгт мөрийн дэд мөрийг л устгаж чадна. Илүү тодорхой хэлвэл, та $w$-н хэд хэдэн үргэлжилсэн элементийг сонгож чадах ба дарааллаас тэдгээр элементээ устгана. $w_{l}, w_{l + 1}, ..., w_{r}$-г дарааллаас сонгосон элементүүд гэж үзье. Эдгээр нь дараах нөхцлийг хангах ёстой:

• $(l ≤ i < r)$ байх дурын $i$-н хувьд $|w_{i} - w_{i + 1}| = 1$ тэнцэтгэл үнэн байна;
• $(l ≤ i < r)$ байх дурын $i$-н хувьд $2*w_{i} - w_{i + 1} - w_{i - 1} ≥ 0$ тэнцэтгэл биш үнэн байх ёстой.

$w$-с сонгосон дэд мөрийг устгасны дараа та $v_{r - l + 1}$ оноо авна. Тодорхойлсон үйлдлийг хэд хэдэн удаа гүйцэтгэж болох бөгөөд энэ тохиолдолд тохирох дэд мөр байна. Мөн та тоглоомыг хэзээ ч дуусгаж болно. Таны даалгавар бол тоглоомоос авж чадах хамгийн их оноог тооцоолох юм.

Оролт

Эхний мөрөнд $w$ дарааллын анхны урт болох $n$ $(1 ≤ n ≤ 400)$ бүхэл тоог оруулна. Дараагийн мөрөнд үйлдлүүдийн өртөг болох $n$ ширхэг бүхэл $v_{1}, v_{2}, ..., v_{n}$ $(0 ≤ |v_{i}| ≤ 2000)$ тоонууд байна. Гуравдугаар мөрөнд анхны $w$ дараалалыг тодорхойлох $n$ ширхэг $w_{1}, w_{2}, ..., w_{n}$ $(1 ≤ w_{i} ≤ 10^{9})$ бүхэл тоонууд байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь таны авч чадах хамгийн их оноо юм.