1136 : ขนม (snack)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

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

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

  • หลังจากย้ายแล้ว ถุงแต่ละใบต้องจะมีขนมเหลืออยู่อย่างน้อย 1 ชิ้น
  • หลังจากย้ายแล้ว ค่าเฉลี่ยของราคาขนมในถุงแต่ละใบจะต้องมีค่าเพิ่มขึ้นจากเดิม

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

ตัวอย่างเช่น หากในตอนเริ่มต้น ถุงใบแรกมีขนมราคา 4, 6, 10, 15 และ 20 บาท ซึ่งมีค่าเฉลี่ยเป็น 11 บาท ส่วนถุงใบที่สองมีขนมราคา 3 และ 5 บาท ซึ่งมีค่าเฉลี่ยเป็น 4 บาท คุณสามารถย้ายขนมราคา 10 บาท จากถุงใบแรกไปยังใบที่สองได้ ซึ่งจะทำให้ค่าเฉลี่ยของราคาขนมในถุงใบแรกเพิ่มเป็น 11.25 บาท และใบที่สองเพิ่มเป็น 6 บาท แต่หลังจากนั้น คุณจะไม่สามารถย้ายขนมชิ้นใดๆ ให้สอดคล้องตามเงื่อนไขได้อีกแล้ว ดังนั้น คุณจึงย้ายขนมได้เพียงครั้งเดียว

แต่วิธีดังกล่าวยังไม่ใช่วิธีที่ดีที่สุด หากคุณเริ่มต้นด้วยการย้ายขนมราคา 6 บาท จากถุงใบแรกไปยังใบที่สอง ค่าเฉลี่ยของราคาขนมในถุงใบแรกจะเพิ่มเป็น 12.25 บาท และใบที่สองจะเพิ่มเป็น 4.67 บาท จากนั้น คุณจึงย้ายขนมราคา 10 บาท จากถุงใบแรกไปยังใบที่สอง ทำให้ค่าเฉลี่ยของราคาขนมในถุงใบแรกเพิ่มเป็น 13 บาท และใบที่สองเพิ่มเป็น 6 บาท คุณจึงย้ายขนมได้ทั้งหมด 2 ครั้ง ซึ่งวิธีนี้เป็นวิธีที่ทำให้ย้ายขนมตามเงื่อนไขได้มากครั้งที่สุดแล้ว

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม A และ B (1 ≤ A,B ≤ 1,000,000) แทนจำนวนขนมตอนเริ่มต้นในถุงใบแรกและใบที่สอง

บรรทัดต่อมาระบุจำนวนเต็มบวก A ตัว แทนราคาของขนมแต่ละชิ้นในถุงใบแรก โดยเรียงจากน้อยไปหามาก

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

ขนมแต่ละชิ้นจะมีราคาไม่เกิน 1,000,000 บาท และขนมแต่ละชิ้นอาจมีราคาเท่ากันได้

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

การให้คะแนน
20% ของข้อมูลทดสอบ จะมี A,B ≤ 10
40% ของข้อมูลทดสอบ จะมี A,B ≤ 1,000 
60% ของข้อมูลทดสอบ จะมี A,B ≤ 100,000

ที่มา
โจทย์โดย: สุธี เรืองวิเศษ


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 2
4 6 10 15 20
3 5
2
4 3
4 6 15 20
3 5 10
0

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

กำลังออนไลน์: 22 ผู้เยี่ยมชมและ 1 สมาชิก (1 บอท)