Problem
Kazuma mengembara dengan tiga sahabat: Aqua, Megumin, dan Darkness. Tetapi perjalanan tidak dibayar, jadi skuad kami mesti menyelesaikan tugas yang diberikan oleh Persatuan Pengembara.
Kazuma telah memilih n tugasan untuk diselesaikan. Bagaimanapun, setiap kali skuad dengan kekuatan penuh mengambil sesuatu, perkara yang tidak dijangka dan tidak masuk akal berlaku. Itulah sebabnya Kazuma memutuskan bahawa untuk setiap tugas dia akan mengambil
tepat dua teman.
Nisbah setiap sahabat kepada Kazuma dicirikan oleh integer. Pada mulanya, sikap masing-masing adalah neutral dan sama dengan 0. Dalam proses menyiapkan tugasan, sikap gadis-gadis yang dia pikul terhadapnya berubah ke arah positif atau negatif (atau mungkin tidak berubah sama sekali) .
Untuk setiap tugasan, Kazuma tahu bagaimana sikap setiap gadis terhadapnya akan berubah selepas menyelesaikan tugas itu. Dia mahu mengambil teman dalam tugasan supaya selepas menyelesaikan semuanya, sikap semua gadis terhadapnya adalah sama. Jika ini boleh dicapai dengan cara yang berbeza, maka, sudah tentu, hubungan itu perlu sebaik mungkin.
Bantu Kazuma memikirkan layanan paling sama rata yang dia boleh dapatkan untuk semua gadis.
Input:
Baris pertama mengandungi integer positif n (1 ≤ n ≤ 25) — bilangan tugasan yang perlu diselesaikan.
N baris seterusnya mengandungi penerangan tentang — baris ke-i mengandungi tiga nombor a
i, m
i, d
i — jumlah yang mana sikap Aqua, Megumin atau Darkness terhadap Kazuma akan berubah, masing-masing, jika wira membawa mereka bersamanya untuk menyelesaikan tugas ke-i.
Semua nombor dalam input adalah integer dan tidak melebihi 10
7 dalam nilai mutlak.
Output:
Jika tiada penyelesaian, cetak "Mustahil" dalam baris pertama.
Jika tidak, cetak hubungan yang akan dimiliki oleh semua gadis terhadap Kazuma, dan pada masa yang sama, cetak maksimum yang mungkin.
Contoh:
| Input |
Output |
3
1 0 0
0 1 0
0 0 1
| 1 |
7
0 8 9
5 9 -2
6-8-7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7
| 5 |
2
1 0 0
1 1 0
| Mustahil |