Có ~n~ khối đá, đánh số từ 1 đến ~n~. Khối thứ ~i~ là một hình hộp chữ nhật mỏng, mặt đáy và mặt trên đều là hình chữ nhật kích thước ~a_i \times b_i~, và khối có giá trị ~g_i~ đồng.

Ta muốn xếp một số khối (có thể không dùng hết) chồng lên nhau thành một tháp theo các quy tắc sau:

• Mặt đáy của khối đặt phía trên phải nằm trọn vẹn trong mặt trên của khối ngay phía dưới nó (được phép có cạnh bằng nhau, tức là hai kích thước của khối trên đều không vượt quá hai kích thước tương ứng của khối dưới).
• Các cạnh của hai khối chồng lên nhau phải song song với nhau (có thể xoay khối trong mặt phẳng ngang để các cạnh song song, tức là khối trên có thể đặt theo chiều ~a \times b~ hoặc ~b \times a~).

Hãy chọn cách xây tháp sao cho tổng giá trị các khối được dùng là lớn nhất và in ra tổng đó.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 100~) là số khối đá.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~a_i, b_i, g_i~ (~1 \le a_i, b_i, g_i \le 10^4~) là kích thước mặt đáy và giá trị của khối thứ ~i~.

Kết quả

• In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể.

Ví dụ

TOWER.INP

3
3 4 3
5 2 4
2 3 5

TOWER.OUT

9

Giải thích: Đặt khối 3 (đáy ~2 \times 3~, giá trị 5) lên khối 2 (đáy ~5 \times 2~, giá trị 4), tổng giá trị là 9. Hình minh họa trong sách thể hiện khối đáy ~3 \times 4~, khối ~5 \times 2~ và khối ~2 \times 3~, kết quả là tháp hai tầng gồm khối 2 ở dưới, khối 3 ở trên.