JOI2013

watching

มีกิจกรรม (event) ทางวัฒนธรรมมากมายในออสเตรเลีย เช่น กีฬาและสัตว์นานาชนิต คุณพยายามจะเข้าชมกิจกรรมต่าง ๆ บนถนนใน Brisbane

ถนนถูกแบ่งเป็น 1 000 000 000 ส่วน แต่ละส่วนมีหมายเลข 1,2,...,1 000 000 000 จากทิศตะวันตกไปยังตะวันออก คุณต้องการดูกิจกรรม N กิจกรรม กิจกรรมที่ i อยู่ที่ส่วนที่ Ai

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