Problem
Di Interregional Robot Programming Olympiad, pertandingan diadakan dalam satu pusingan dan dalam format yang luar biasa. Tugasan diberikan kepada peserta secara berurutan, bukan semuanya pada awal pusingan, dan setiap tugasan ke-i (1 ≤ i ≤ n) tersedia kepada peserta pada masanya s
i. Setelah menerima tugasan seterusnya, setiap peserta mesti segera menentukan sama ada dia akan menyelesaikannya atau tidak. Jika dia memilih untuk menyelesaikan masalah ini, maka dia mempunyai t
i minit untuk menyerahkan penyelesaiannya untuk pengesahan, dan pada masa ini dia tidak boleh beralih kepada menyelesaikan masalah lain. Sekiranya peserta enggan menyelesaikan masalah ini, maka pada masa akan datang dia tidak boleh kembali kepadanya. Pada masa apabila masa yang diperuntukkan untuk tugasan yang peserta selesaikan telah tamat, dia boleh mula menyelesaikan tugasan lain yang tersedia pada masa yang sama, jika ada tugasan sedemikian, atau menunggu tugas lain muncul. Pada masa yang sama, untuk penyelesaian yang betul bagi masalah ke-i, peserta menerima mata c
i.
Artur, yang mewakili salah satu pusat kecerdasan buatan serantau di Olimpik antara wilayah, memahami bahawa bukan sahaja keupayaan untuk menyelesaikan masalah, tetapi juga pengiraan strategik yang betul mengenai masalah yang perlu diselesaikan dan yang mana yang perlu dilangkau, memainkan peranan penting dalam seperti Olimpik. Dia, seperti semua peserta, sebelum permulaan lawatan tahu pada masa yang mana setiap tugas akan tersedia, berapa banyak masa yang akan diperuntukkan untuk penyelesaiannya dan berapa banyak mata yang anda boleh dapatkan untuk menyelesaikannya. Artur ialah pelajar yang berbakat dan oleh itu akan berjaya menyelesaikan sebarang masalah yang dia pilih untuk diselesaikan di Olympiad dalam masa yang ditetapkan dan lulus untuk pengesahan.
Ia dikehendaki menulis program yang menentukan bilangan maksimum mata yang Arthur boleh dapat dengan pilihan optimum masalah yang akan diselesaikannya, serta bilangan dan senarai masalah tersebut.
Input
Baris pertama mengandungi satu integer n (1 ≤ n ≤ 10
5) bilangan masalah dalam Olympiad.
N baris seterusnya mengandungi penerangan tentang masalah, tiga nombor pada setiap baris: si saat masalah ke-i muncul dalam beberapa minit, t
i masa yang diperuntukkan untuk penyelesaiannya dalam beberapa minit, dan ci berapa banyak mata yang akan diterima peserta untuk menyelesaikan masalah ini (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Cetakan
Baris pertama mesti mengandungi satu nombor – bilangan maksimum mata yang Arthur boleh perolehi di Olympiad.
Baris kedua harus mengandungi satu integer m - bilangan tugasan yang perlu diselesaikan dengan pilihan optimum.
Baris ketiga harus mengandungi m integer yang dipisahkan ruang - bilangan masalah ini mengikut urutan penyelesaiannya. Tugasan dinomborkan, bermula dari satu, mengikut susunan yang diterangkan dalam fail input.
Jika terdapat beberapa jawapan yang optimum, cetak mana-mana daripadanya.
Contoh
| # |
Input |
Output |
| 1 |
2
1 1 1
2 2 2
| 3
2
1 2
|
| 2 |
3
1 2 1
3 2 1
2 4 3
| 3
1
3 |