Sikkə kolleksiyası
Kolleksiyaçıların klubunda n nəfər iştirak edir. Klub XIX əsr sikkələrinin tam kolleksiyasını ilk toplayan şəxs üçün müsabiqə keçirir. Klubun qaydalarına görə, bu kolleksiya m müxtəlif növ sikkədən ibarət olmalıdır, yəni hər növdən ən azı bir dənə olmaqla, bir neçə sikkə ola bilər.
Vasya bu məsələyə ciddi yanaşmaq qərarına gəlib və sikkə mübadiləsi üçün optimal strategiyanı hesablamaq istəyir. O bilir ki, hər hansı bir kolleksiyaçı öz sikkəsini a Vasya'nın sikkəsi b ilə məmnuniyyətlə dəyişər, amma yalnız bir halda: əgər bu kolleksiyaçının a növündən bir neçə sikkəsi varsa, amma b növündən hələ heç bir sikkəsi yoxdursa. Kolleksiyaçılar başqa heç bir mübadiləyə razı deyillər. Vasya isə, digərlərindən fərqli olaraq, qlobal optimallaşdırmanı yerli optimallaşdırmadan üstün tutur və istədiyi halda bu qaydanı poza bilər.
Vasya belə mübadilələr vasitəsilə mümkün qədər çox müxtəlif növ sikkə toplamaq istəyir ki, gələcəkdə müsabiqədə qalib gəlmək vəzifəsini asanlaşdırsın. Ona sikkə mübadiləsi üçün optimal strategiyanı hesablamağa kömək edin!
Giriş verilənləri
Giriş faylının ilk sətirində iki ədəd n və m (1 ≤ m, n ≤ 100) verilir. Sonra n sətir, hər birində m ədəd var: i-ci sətirin j-ci ədədi i-ci kolleksiyaçının j-ci növ sikkələrinin sayıdır. Bu ədədlərin hamısı qeyri-mənfi və 1000-dən çox deyil. Vasya'nın nömrəsi 1-dir.
Çıxış verilənləri
Çıxış faylının ilk sətirində toplana biləcək maksimum müxtəlif növ sikkələrin sayını göstərin. Sonra belə bir sayda müxtəlif növ sikkə əldə etməyə aparan mübadilə ardıcıllığını göstərin. Hər bir mübadilə x_i, u_i, v_i formatında göstərilir, burada x_i – mübadilə ediləcək kolleksiyaçının nömrəsi, u_i – Vasya'nın ondan alacağı sikkənin nömrəsi, v_i – Vasya'nın ona verəcəyi sikkənin nömrəsidir.