2031 : HIRING
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 64 megabyte(s)

คุณจำเป็นต้องจ้างคนงานเพื่อโครงการก่อสร้าง มีผู้สมัครเพื่อเข้าทำงานนี้จำนวน N คนและถูกนับเป็นหมายเลขตั้งแต่คนที่ 1 ถึงคนที่ N โดยในแต่ละผู้สมัคร ผู้สมัครคนที่ k จะเรียกร้องว่า ถ้าหากเขาได้รับการว่าจ้าง เขาจะต้องได้รับค่าตอบแทนอย่างน้อยที่สุด S_k ดอลลาร์ นอกจากนี้ ผู้สมัครคนที่ k จะมีระดับคุณวุฒิเท่ากับ Q_k และข้อบังคับของอุตสาหกรรรมก่อสร้างได้กำหนดว่า คุณจะต้องจ่ายค่าตอบแทนแก่คนงานของคุณเป็นสัดส่วนโดยตรงกับระดับคุณวุฒิของพวกเขา ซึ่งสัมพันธ์กับระดับของแต่ละคน ยกตัวอย่างเช่น ถ้าคุณจ้างคนงาน 2 คนคือ A และ B และ Q_A = 3 * Q_B แล้ว คุณจะต้องจ่ายค่าตอบแทนแก่คนงาน A เป็นจำนวน 3 เท่าพอดิบพอดีของจำนวนที่คุณจ่ายแก่คนงาน B คุณสามารถจ่ายค่าตอบแทนแก่คนงานของคุณเป็นจำนวนเงินที่ไม่ใช่จำนวนเต็มได้ ซึ่งในกรณีนี้จะรวมถึงจำนวนที่ไม่สามารถที่จะเขียนด้วยจำนวนจำกัดของตัวเลขในรูปฐานสิบ เช่น 1 ใน 3 หรือ 1 ใน 6 ของดอลลาร์

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

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

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

เงื่อนไข
1 ≤ N ≤ 500 000 คือ จำนวนของผู้สมัคร
1 ≤ S_k ≤ 20 000 คือ ความต้องการเงินเดือนขั้นต่ำของผู้สมัครคนที่ k
1 ≤ Q_k ≤ 20 000 คือ ระดับคุณวุฒิของผู้สมัครคนที่ k
1 ≤ W ≤ 10 000 000 000 คือ จำนวนเงินที่คุณมีอยู่

*หมายเหตุ: ค่าสูงสุดของ W ไม่สามารถใช้ในรูปแบบ 32 บิตได้ คุณจะต้องใช้ชนิดของข้อมูลแบบ 64 บิต เช่น long long ใน C/C++ หรือ int64 ใน Pascal เพื่อที่จะเก็บค่า W ในตัวแปรเพียงตัวเดียวได้ สำหรับรายละเอียดเพิ่มเติมโปรดดูใน Technical info sheet

ข้อมูลนำเข้า
โปรแกรมของคุณจะต้องอ่านข้อมูลจากคีย์บอร์ด (standard input) ดังนี้

• ในบรรทัดแรก ประกอบด้วยเลขจำนวนเต็ม N และ W ซึ่งแยกกันโดยใช้ช่องว่าง
• แต่ละ N บรรทัดถัดมา จะอธิบายถึงผู้สมัครแต่ละคน ผู้สมัคร 1 คนต่อ 1 บรรทัด โดยบรรทัดที่ k ของบรรทัดเหล่านี้จะอธิบายถึงผู้สมัครคนที่ k ซึ่งประกอบด้วยเลขจำนวนเต็ม S_k และ Q_k แยกกันด้วยช่องว่าง

ข้อมูลส่งออก
โปรแกรมของคุณจะเขียนข้อมูลออกมาทางจอภาพ (standard output) ดังนี้

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

ที่มา: 21st International Olympiad In Informatics– August 8 - 15, 2009 (Day 1) :: Modify เล็กน้อย (:

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
4 100 5 1000 10 100 8 10 20 1	2
3 4 1 2 1 3 1 3	3
3 40 10 1 10 2 10 3	2

ความช่วยเหลือ: Hint[1]  Hint[2]  Hint[3]