1093 : หยิบหนังสือ
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)

เนื่องจากคุณมาเข้าแถวสาย คุณจึงโดนทำโทษให้จัดหนังสือในห้องสมุด หนังสือแต่ละเล่มที่คุณจัดล้วนแต่เป็นหนังสือเรียนหนา ๆ น่าเบื่อ  ทันทีที่ถึงเวลาพักเที่ยงและอาจารย์ห้องสมุดของคุณไม่อยู่ คุณจึงคิดเกมหนึ่งขึ้นมาเล่นกับตัวเอง

เกมนี้คุณคิดเองเล่นเองคนเดียว เริ่มต้นจากมีหนังสืออยู่ n เล่มวางเรียงอยู่บนกองเดียวกันกองหนึ่ง หนังสือแต่ละเล่มถูกติดหมายเลขไว้บนสันปก ซึ่งเป็นจำนวนเต็มไม่ติดลบซึ่งมีค่าไม่เกิน 1,000,000

คุณสามารถหยิบหนังสือออกจากได้ทีละสามเล่มที่อยู่ติดกัน  แต้มที่ได้จากการหยิบหนังสือหนึ่งครั้งเกิดจากการนำหมายเลขของหนังสือสองเล่มบนรวมกันแล้วหักด้วยหมายเลขของหนังสือเล่มล่าง  คุณสามารถหยิบหนังสือออกมาได้หลาย ๆ ครั้ง เพื่อทำให้ผลรวมแต้มของการหยิบหนังสือออกมามีค่ามากที่สุดเท่าที่ทำได้  อนึ่งคุณไม่จำเป็นต้องหยิบหนังสือออกจนหมดทั้งกอง

งานของคุณ

    จงเขียนโปรแกรมรับหมายเลขของหนังสือ n เล่มในกองจากบนลงล่าง แล้วให้ตอบผลรวมแต้มที่มากที่สุดที่ทำได้จากการหยิบหนังสือนี้

ข้อมูลนำเข้า

    บรรทัดที่ 1 มีจำนวนเต็มบวก N (1≤N≤2,000) แทนจำนวนหนังสือในกอง
    บรรทัดที่ 2 ถึงบรรทัดที่ N+1 จะบอกหมายเลขหนังสือในกอง จากบนลงล่าง บรรทัดละหนึ่งจำนวน ซึ่งจำนวนเต็มไม่ติดลบดังกล่าวมีค่าไม่เกิน 1,000,000

ข้อมูลส่งออก

    มีจำนวนเต็มจำนวนเดียวแต้มรวมที่มากที่สุดที่เป็นไปได้จากการหยิบหนังสือตามเงื่อนไข

โจทย์โดย: วรภัทร จรางกูล
ที่มา: ดัดแปลงจากข้อสอบพี่ช่วยน้อง โรงเรียนมหิดลวิทยานุสรณ์ พ.ศ. 2552

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
7 1 2 3 4 5 6 7	5
9 5 5 5 5 5 5 5 5 100	10
15 28 40 39 88 37 46 18 25 39 50 67 40 19 74 23	385

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้