ในโรงเรียนแห่งหนึ่ง นักเรียนที่นี่รักการโดดเรียนเป็นชีวิตจิตใจ อย่างไรก็ตาม โรงเรียนแห่งนี้มีกฎเหล็กคือ “นักเรียนคนหนึ่งสามารถโดดเรียนได้เพียงวันละ k ครั้งเท่านั้น โดยแต่ละครั้งจะต้องโดดเรียนไม่มากกว่า p คาบติดกัน แต่จะต้องเข้าเรียนอย่างน้อย 1 คาบในแต่ละวัน” กล่าวอีกนัยหนึ่งได้ว่า นักเรียนสามารถเริ่มต้นโดดเรียนได้ k ครั้งโดยแต่ละครั้งจะโดดเรียนได้อย่างมาก p คาบติดกันแต่ไม่สามารถโดดเรียนทุกคาบเรียนได้

            Note การโดดเรียนแต่ละครั้งอาจกระทำต่อเนื่องกันได้ (พูดง่ายๆคือสามารถโดดเรียนติดกัน p*k คาบได้หากต้องการ)

            เป็นที่รู้กันในโรงเรียนว่าแต่ละคาบเรียนนั้น คาบเรียนมีความ “น่าเบื่อ” มากเพียงใด โดยคาบเรียนหนึ่งๆจะมีค่าความน่าเบื่อเฉพาะตัวแต่ละคาบ

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

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

บรรทัดแรกประกอบด้วยจำนวนนับ n, k และ p แทนจำนวนคาบ, จำนวนครั้งที่สามารถโดดได้ และความยาวนานของการโดดแต่ละครั้ง ( 1 < n < 1000 000 , 1 < k < 1000 000 , 1 < p < 1000 000 )

บรรทัดถัดมา n บรรทัดเป็นเลขจำนวนนับบรรทัดละ 1 จำนวน โดยบรรทัดที่ 1+i จะแสดงค่าความน่าเบื่อของคาบเรียนที่ i (1< ค่าความน่าเบื่อคาบที่ i < 1000 000 000 )

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

บรรทัดแรกและบรรทัดเดียวแสดงค่าของความน่าเบื่อที่มากที่สุด เมื่อคุณจัดการโดดเรียนแบบ ค่าของความน่าเบื่อของคาบที่เข้าเรียนที่น่าเบื่อมากที่สุดมีค่าน้อยที่สุด

โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int )

ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์