HT AIRLINE là một hãng hàng không danh tiếng ở Việt Nam, tuy nhiên, để tồn tại trong cơn bão suy thoái kinh tế, Ban giám đốc quyết định giảm chi phi tiền lương cho phi công càng nhiều càng tốt.

HT airline có tất cả ~ n ~ phi công ( ~ n ~ là số chẵn), các phi công được đánh số từ 1 đến ~ n ~. HT airline cần chính xác ~ n/2 ~ phi hành đoàn, mỗi phi hành đoàn gồm 2 phi công (một lái chính và một lái phụ), lái chính phải nhiều giờ bay hơn lái phụ. Hợp đồng mà công ty ký với các phi công có 2 điều khoản rõ ràng: tiền lương khi là lái chính và tiền lương khi là lái phụ. Rõ ràng, đối với 1 phi công, tiền lương lái chính bao giờ cũng cao hơn tiền lương khi lái phụ. Tuy nhiên, với một phi hành đoàn, có thể tiền lương của lái chính lại thấp hơn lái phụ.

Để giảm chi phí trả tiền lương, HT phải xác định một cách phân chia tối ưu ~ n/2 ~ phi hành đoàn.

Bạn hãy giúp HT viết chương trình xác định số tiền tối thiểu để trả lương cho ~n~ phi công.

Dữ liệu vào

• Dòng 1: Số nguyên dương ~ n ~, là số phi công ở HT airline.
• ~ n ~ dòng tiếp theo, dòng thứ ~ i ~ là thông tin về phi công ~ i ~: gồm ba số ~ t, a ~ và ~ c ~ viết cách nhau 1 dấu cách, tương ứng là số giờ bay, tiền lương khi lái chính và tiền lương khi lái phụ. Số giờ bay của phi công là đôi một khác nhau.

Kết quả

Một số nguyên duy nhất là tiền lương tối thiểu phải trả cho ~ n ~ phi công.

Ràng buộc

• ~2≤n≤100000;~ ~n~ là số chẵn
• ~1≤c≤a≤100000~
• ~100≤t≤100000~

Ví dụ:

Input 1

6
1000 10000 7000
1028 9000 3000
3056 6000 4000
8934 5000 1000
10231 9000 3000
11200 8000 6000 

Output 1

32000