CPFED жиынында балалар бірнеше командаға бөлініп, «Командалық Ним» ойынын ойнауды шешті. Бұл классикалық Ним ойынындағыдай тастарды пайдаланатын өте бәсекелестік ойын. Сондықтан командалар арасындағы симпатия көрсеткіші белгілі бір шекті аспау үшін командаларға бөліну керек, әйтпесе қарсыластар бір-біріне жанашырлық танытады. Ал \[\text{командалық ним -- аяусыз ойын.}\] bthero ең жақсы командалық бөлуді ұйымдастыруға көмектесуге шешім қабылдады. Ойында \(n\) адам ойнайды және кейбір жұп ойыншылар үшін екіжақты (екіжақты) симпатия деңгейі \((a,b)\) белгілі, ол \(simp(a,b)\) саны арқылы көрінеді. Қалған ойыншылардың жұптары арасындағы симпатияны нөлге тең деп санауға болады. Командалар арасындағы симпатия деңгейі әртүрлі командалардың қатысушылары арасындағы симпатиялардың қосындысына тең. Формальды түрде, \(S\) және \(T\) командалары арасындағы симпатия деңгейі келесідей: \[simp(S, T) = \sum_{a \in S} \sum_{b \in T} simp(a,b).\] Ойынды қызықты ету үшін, осы ойынды жасаушы bthero командалар арасындағы симпатияның әмбебап шегін \(W\) деп есептеді, бұл командалар бір-біріне жанашырлық танытпайтын, бірақ достық атмосфера сақталатын деңгей. Енді ол сізден ойыншыларды мүмкіндігінше көп топтарға бөліп, командалар арасындағы симпатия деңгейі осы шекті аспауы үшін сұрайды.

Енгізу

Бірінші жолда 3 сан бар: \(n\), \(m\) және \(W\) (\(1 \le n \le 2000\), \(1 \le m \le \frac{n \cdot (n - 1)}{2}\), \(1 \le W \le 10^9\)) – ойыншылар саны, симпатиясы бар жұптар саны және идеалды симпатия шегі.

Келесі \(m\) жолдың әрқайсысында үш саннан тұратын триплет бар. \(i\)-ші жолда \(a_i\), \(b_i\), \(w_i\) сандары бар (\(1 \le a_i, b_i \le n\), \(a_i \neq b_i\)) – \((a_i, b_i)\) ойыншылар жұбының өзара симпатиясы \(simp(a_i,b_i) = w_i\). \((a, b)\) және \((b, a)\) жұптары жалпы бір реттен артық кездеспейтіні кепілдендірілген.

Шығару

Бір жолда – ойыншыларды бөліп алуға болатын командалардың ең көп санын шығарыңыз, бұл ретте командалар арасындағы симпатия шегі аспайды.

Мысалдар

Енгізу 1

6 8 6
1 2 4
1 5 7
4 5 1
5 2 4
2 6 5
3 4 6
3 6 1
4 6 9

Жауап 1

2

Ескертпелер

Бірінші мысалда бірінші командада \(1,2,5\), ал екінші командада \(3,4,6\).