เจลลี่บีน (acm15_jellybean)

• Problem
• Submit
• Status
• Discussion
• Solution
• Analytics

Time limit:

1000 ms

Memory limit:

256 MB

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

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

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

Input

บรรทัดแรก ประกอบด้วยจำนวนเต็ม T (1 ≤ T ≤ 10) ระบุจำนวนวันที่สนใจ ซึ่งในแต่ละวันจะประกอบด้วยข้อมูลต่าง ๆ ดังรูปแบบต่อไปนี้

บรรทัดแรก ประกอบด้วยจำนวนเต็ม J และ N (1 ≤ J, N ≤ 1,000) แทนจำนวนขนม Jelly Bean ที่ได้จากโรงงานในวันนั้น ๆ และจำนวนกล่องที่มี

อีก N บรรทัดต่อมา ระบุจำนวนเต็ม R_i และ C_i (1 ≤ R_i, C_i ≤ 10,000) แทนจำนวนแถวและจำนวนหลักของกล่องที่ i (อาจมีกล่องที่มีขนาดซ้ำกัน) ซึ่งกล่องดังกล่าวจะสามารถบรรจุขนมได้ R_i * C_i ชิ้น

Output

มี T บรรทัด แต่ละบรรทัดระบุจำนวนกล่องที่น้อยที่สุดที่ต้องใช้ในวันที่ i

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B