นายเมธาต้องการทำการทดลองทางวิทยาศาสตร์อยู่สองงาน โดยที่แต่ละงานประกอบด้วยขั้นตอนทั้งหมด N
ขั้นตอน คือขั้นตอน  J1,J2,J3,..,JN สำหรับงานแรก และ ขั้นตอน K1,K2,K3,...,KN สำหรับงานที่สอง ซึ่งแต่ละขั้นตอนอาจใช้เวลาเท่ากันหรือต่างกันก็ได้ อย่างไรก็ตามขั้นตอนในงานเดียวกันไม่สามารถสลับลำดับกันได้ กล่าวคือ สำหรับงานแรก ขั้นตอน J1 จะต้องถูกทำเป็นอันดับแรก และขั้นตอน J2,J3,...,JN จะถูกทำต่อมาตามลำดับดังกล่าว สำหรับงานที่สองก็เช่นกัน ขั้นตอน K1 จะต้องถูกทำเป็นอันดับแรก และขั้นตอน K2,K3,...,KN จะถูกทำตามลำดับ

แม้จะไม่สามารถสลับลำดับขั้นตอนในงานเดียวกันได้ แต่เมธาก็สามารถสลับลำดับขั้นตอนระหว่างงานแรกกับงานที่สองได้ เป็นต้นว่าถ้า N=3 เมธาสามารถที่จะทำการทดลองในลำดับK1,K2,J1,K3,J2,J3 เพราะลักษณะนี้เป็นการทำการทดลองแต่ละงานตามลำดับจากขั้นตอนแรกไปขั้นตอนสุดท้าย

โชคไม่ดีนัก เมธาพบว่าห้องปฏิบัติการมีเครื่องมือสำหรับทำการทดลองอยู่เพียงชุดเดียว และงานทั้งสองก็ต้องใช้เครื่องมือชุดเดียวกันนี้  ยิ่งไปกว่านั้นเครื่องมือสามารถทำงานได้เพียง M นาทีในแต่ละวัน และการทดลองแต่ละขั้นตอนก็ต้องดำเนินการอย่างต่อเนื่องให้สำเร็จภายในวันเดียวเท่านั้น

ยกตัวอย่างเช่น หากงานแต่ละงานมีสองขั้นตอน N=2 และใช้เครื่องได้ 300 นาทีต่อวัน
 M=300 เมื่อ J1=200, J2=150, K1=50 และ K2=150 ถ้าหากเมธาจัดลำดับการทดลองเป็น J1,J2,K1,K2 ตามลำดับ ขั้นตอน J2 จะไม่สามารถทำได้ในวันแรกเพราะเวลารวมในวันแรกจะเกิน
300 นาที ทำให้ต้องเลื่อนไปทำในวันที่สอง และการทดลองตามลำดับนี้ จะใช้เวลาทั้งหมด 3 วัน โดยวันสุดท้าย (วันที่สาม) จะใช้เวลาทั้งหมด 150 นาที แต่หากเมธาจัดลำดับการทดลองใหม่เป็น J1,K1,K2,J2 การทดลองทั้งหมดจะแล้วเสร็จในเวลาเพียง 2 วัน โดยวันสุดท้าย (วันที่สอง) จะใช้เวลาทั้งหมด 300 นาที

จงเขียนโปรแกรมที่มีประสิทธิภาพในการจัดลำดับขั้นตอนการทดลองที่ทำให้การทดลองทั้งสองงานเสร็จด้วยเวลาที่น้อยที่สุด

ข้อมูลเข้า

1.       บรรทัดแรกเป็นเลขจำนวนเต็ม M ระบุเวลาที่สามารถใช้เครื่องมือได้ในแต่ละวัน
โดยที่ 1 < M < 600 และ M มีหน่วยเป็นนาที

2.       บรรทัดที่สองเป็นจำนวนเต็ม N ระบุจำนวนขั้นตอนในแต่ละงานโดยที่ 2 < N < 1000

3.       บรรทัดที่สามเป็นจำนวนเต็มบวก N จำนวน คือ a1,a2,a3,...,an แต่ละตัวคั่นด้วยช่องว่าง จำนวนแต่ละจำนวนนี้แทนเวลาที่ต้องใช้ทำการทดลองขั้นตอน J1,J2,J3,...,JN ของงานแรกตามลำดับ มีหน่วยเป็นนาที จำนวนแต่ละจำนวนถูกคั่นด้วยช่องว่าง โดยที่ 1 < ai < M, i = 1,...,N

4.       บรรทัดที่สี่เป็นจำนวนเต็มบวก N จำนวนในลักษณะเดียวกับบรรทัดที่สาม แต่จำนวนเหล่านี้แทนเวลาที่ต้องใช้ในการทดลองขั้นตอน K1,K2,K3,...,KN สำหรับงานที่สอง ซึ่งเวลาเหล่านี้มีค่ามากกว่าหรือเท่ากับหนึ่งและน้อยกว่าหรือเท่ากับ M

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

ข้อมูลส่งออกระบุจำนวนวันที่ต้องใช้ในการทดลองของเมธา และจำนวนนาทีที่ใช้ในการทดลองวันสุดท้าย โดยข้อมูลส่งออกต้องอยู่ในรูปแบบดังต่อไปนี้

1.       บรรทัดแรกระบุจำนวนวันที่ต้องใช้ในการทดลองเป็นจำนวนเต็ม

2.       บรรทัดที่สองระบุจำนวนนาทีที่ใช้สำหรับการทดลองในวันสุดท้าย โดยที่จำนวนนาทีนี้มีค่าตั้งแต่หนึ่งและไม่เกิน M

หมายเหตุ  เวลาในการทดลองที่ดีที่สุดถือตามจำนวนวันเป็นลำดับแรก ในกรณีที่การจัดลำดับขั้นตอนสองแบบใช้จำนวนวันเท่ากัน จะนับเวลาที่ดีที่สุดจากจำนวนนาทีที่ใช้ในวันสุดท้าย


ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 8 (SUTOI8)