Şahmat
Petr Pyaçkin şahmat oyununa maraq göstərdi. Tanınmış ustaların oyunları ilə tanış olmaq üçün o, paytaxt komandasının Böyük Olimpiya kəndi komandasına qarşı dostluq matçının bütün oyunlarını izləmək qərarına gəldi.
Hər bir oyunçunun oyun səviyyəsi var və bu, natural ədədlə ifadə olunur. İki oyunçu yalnız fərqli komandaların üzvü olduqda və onların oyun səviyyəsi d — müəyyən bir qeyri-mənfi tam ədəddən çox fərqlənmədikdə bir-biri ilə oynaya bilər. Hər oyunda hər komandadan bir şahmatçı iştirak edir və onlar bir-biri ilə oynaya bilərlər. Hər bir oyunçu ən çox bir oyunda iştirak edə bilər.
Petr mümkün qədər çox görüşdə iştirak etmək istəyir. Buna görə də o, tanış bir sehrbazdan müdaxilə etməsini xahiş etdi: kənd komandasının bütün oyunçularının oyun səviyyəsini elə bir tam ədəd qədər dəyişsin ki, mümkün oyunların sayı maksimum artsın. Qeyd edək ki, sehrbazın müdaxiləsindən sonra bəzi oyunçuların səviyyələri mənfi ola bilər.
Bütün oyunçuların səviyyələrini və d ədədini bilə-bilə:
kənd oyunçularının oyun səviyyəsini nə qədər dəyişmək lazımdır ki, mümkün olan ən çox oyun oynansın;
bu ən çox oyun sayını keçirmək üçün rəqib komandaların oyunçularını necə cütləşdirmək olar (yalnız belə bir cütləşmənin bir variantını göstərmək lazımdır).
Giriş verilənləri
Giriş faylının ilk sətiri 3 tam ədəd ehtiva edir:
N — kənd komandasının oyunçularının sayı (1 ≤ N ≤ 200);
M — paytaxt komandasının oyunçularının sayı (1 ≤ M ≤ 200);
d — oyun səviyyələrinin fərqi üçün yuxarı hədd, hansı ki oyun oynaya bilərlər (0 ≤ d ≤ 10^9).
Bütün sonrakı ədədlər naturaldır və 10^9 -dan çox deyil.
İkinci sətir N ədəd ehtiva edir — kənd komandasının oyunçularının səviyyələri.
Üçüncü sətir M ədəd ehtiva edir — paytaxt komandasının oyunçularının səviyyələri.
Çıxış verilənləri
Çıxış faylının ilk sətiri iki tam ədəd ehtiva etməlidir: K — sehrbazın uyğun müdaxiləsindən sonra mümkün olan maksimum oyun sayı (hətta heç nəyi dəyişməsə belə) və D — kənd oyunçularının oyun səviyyəsini dəyişmək lazım olan miqdar ki, K oyun oynansın.
Növbəti K sətir K müxtəlif cüt natural ədəd ehtiva etməlidir, hər biri bir sətirdə. Hər bir cüt kənd komandasının oyunçusunun nömrəsi və paytaxt komandasının oyunçusunun nömrəsidir, müvafiq olaraq, hansı ki bir-biri ilə oyun keçirməlidir ki, ümumilikdə K oyun oynansın. Cütləri istənilən ardıcıllıqla çıxarmaq olar.