| برای این سوال هر چقدر ارسال شما بهینهتر باشد، نمرهی بیشتری میگیرید و لزوماً گرفتن نمرهی کامل امکانپذیر نیست. |
|---|
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
روی نقشه شهر گلرنگ \(n\) مرکز خرید وجود دارد، مرکز خریدها با اعداد ۱ تا \(n\) شمارهگذاری شدهاند. مرکز شمارهی \(i\) در نقطهی \((x_i, y_i)\) قرار دارد.
گل آقا عاشق کیک دوقولوی تاینی است. این کیک فقط در مراکز اکلا وجود دارد. میدانیم مرکز \(i\)ام \(a_i\) کیک دارد و از اولین لحظهای که این مقدار تمام شود. \(t\) روز بعد، مجدداً \(a_i\) کیک به این فروشگاه ارسال میشود. هیچ کس جز گل آقا از این کیکها نمیخرد.
حال گل آقا در نقطهی \((0, 0)\) است. سرعت حرکت او \(1\) است. او اکنون \(T\) ثانیه وقت دارد که در شهر بچرخد و بیشترین تعداد کیک را بخرد. از شما میخواهیم برنامهای بنویسید که این بیشترین مقدار را حساب کند.
توجه کنید زمان مراجعهها لزوماً اعداد صحیح نیستند، همچنین باید فاصلهی زمان مراجعه کردن به دو فروشگاه قابل رسیدن باشد. فرض میشود که زمان خرید کردن ناچیز بوده و به مجض مراجعه همهی کیکهای موجود خریداری میشود.
همچنین میتوان نزیک یک فروشگاه ایستاد و چندبار از آن خرید کرد اما باید \(t\) ثانیه از خرید قبلی گذشته باشد.
ورودی
در سطر اول ورودی، سه عدد صحیح \(n\)، \(t\) و \(T\) آمده که تعداد فروشگاهها، زمان شارژ شدن کیک و کل زمانی که گل آقا دارد را نشان میدهد. \[1 \leq n, t \leq 100\] \[1 \leq T \leq 1000\]
در \(n\) سطر بعدی، در هر سطر سه عدد \(x_i\)، \(y_i\) و \(a_i\) آمده که مختصات و تعداد کیکها را نشان میدهد. \[1 \leq x_i, y_i, a_i \leq 100\]
تضمین میشود هیچ دو مرکز اکلا در یک نقطه قرار ندارند.
خروجی
در سطر اول، دو عدد صحیح \(m\) \(k\) چاپ کنید که به ترتیب حداکثر مجموع کیکهایی و تعداد فروشگاههای مراجعه شده را نشان میدهد.
\[0 \leq k \leq 1000\]
در \(k\) سطر بعدی، در هر سطر دو عدد \(d_i\) و \(m_i\) آمده که زمان مراجعه و شمارهی فروشگاه را نشان میدهد. \[0 \leq d_i \leq T\] \[1 \leq m_i \leq n\]
مثالها
ورودی نمونه ۱
4 6 10
1 1 3
5 1 7
1 5 4
5 5 10
خروجی نمونه ۱
20 3
1.414215 1
5.414216 2
9.414217 4
ورودی نمونه ۲
4 6 20
1 1 3
5 1 7
1 5 4
5 5 10
خروجی نمونه ۲
37 5
1.414215 1
5.414216 2
9.414217 4
13.414218 2
17.414219 4