Có $n$ bạn học sinh cùng lúc tìm thầy giáo để hỏi bài. Mỗi bạn đều ước lượng trước thời gian hỏi bài của mình. Thầy giáo có thể sắp xếp thứ tự hỏi bài, các bạn học sinh phải lần lượt vào văn phòng của thầy để hỏi bài.

Quá trình hỏi bài của một bạn học sinh diễn ra như sau:

1. Đầu tiên là vào văn phòng, bạn học sinh số hiệu $i$ cần $s_{i}$ mili giây.

2. Sau đó bạn học sinh đặt câu hỏi và thầy giáo giải đáp, bạn học sinh số hiệu $i$ cần $a_{i}$ mili giây.

3. Hỏi bài xong, bạn học sinh rất vui và sẽ gửi một tin nhắn vào nhóm lớp học, thời gian gửi tin có thể bỏ qua.

4. Cuối cùng bạn học sinh thu dọn đồ đạc và rời khỏi văn phòng, cần $e_{i}$ mili giây. Thường cần $10$ giây, $20$ giây hoặc $30$ giây, tức $e_{i}$ nhận giá trị $10000$, $20000$ hoặc $30000$.

Sau khi một bạn rời khỏi văn phòng, bạn tiếp theo có thể vào văn phòng ngay.

Việc hỏi bài bắt đầu từ thời điểm $0$. Thầy giáo muốn sắp xếp thứ tự hỏi bài một cách hợp lý sao cho tổng các thời điểm gửi tin nhắn vào nhóm lớp của các bạn học sinh là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$, biểu thị số lượng học sinh.

Tiếp theo là $n$ dòng, mô tả thời gian của mỗi bạn học sinh. Trong đó dòng thứ $i$ chứa ba số nguyên $s_{i}, a_{i}, e_{i}$, ý nghĩa như mô tả ở trên.

Dữ liệu ra

In ra một số nguyên, biểu thị tổng nhỏ nhất của các thời điểm mà các bạn học sinh gửi tin nhắn vào nhóm lớp.

Ví dụ

Input

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

Output

280000

Ghi chú

Giải thích ví dụ

Giải đáp theo thứ tự $1,3,2$, thời điểm gửi tin nhắn lần lượt là $20000,80000,180000$.

Quy mô và ràng buộc dữ liệu chấm

Với $30 \%$ test chấm, $1 \leq n \leq 20$.

Với $60 \%$ test chấm, $1 \leq n \leq 200$.

Với mọi test chấm, $1 \leq n \leq 1000,1 \leq s_{i} \leq 60000,1 \leq a_{i} \leq 1000000$, $e_{i} \in{10000,20000,30000}$, tức $e_{i}$ chắc chắn là một trong các giá trị $10000, 20000, 30000$.