Problem
Bölgelerarası Robot Programlama Olimpiyatlarında yarışmalar tek rauntta ve alışılmışın dışında bir formatta yapılıyor. Görevler katılımcılara sıralı olarak verilir, hepsi turun başında değil ve her i-inci görev (1 ≤ i ≤ n) katılımcıların kullanımına s
i. Bir sonraki görevi aldıktan sonra, her katılımcı onu çözüp çözmeyeceğini hemen belirlemelidir. Bu sorunu çözmeyi seçerse, çözümünü doğrulama için göndermek için t
i dakikası vardır ve bu süre zarfında başka bir sorunu çözmeye geçemez. Katılımcı bu sorunu çözmeyi reddederse, gelecekte ona geri dönemez. Katılımcının çözmekte olduğu görev için ayrılan süre sona erdiğinde, eğer varsa aynı anda uygun hale gelen başka bir görevi çözmeye başlayabilir veya başka bir görevin görünmesini bekleyebilir. Aynı zamanda i-inci sorunun doğru çözümü için katılımcı c
i puan alır.
Bölgeler arası Olimpiyatlarda bölgesel yapay zeka merkezlerinden birini temsil eden Artur, yalnızca sorunları çözme yeteneğinin değil, aynı zamanda hangi sorunların çözülmesi ve hangilerinin atlanması gerektiğine dair doğru stratejik hesaplamanın da önemli bir rol oynadığını anlıyor. böyle bir olimpiyat. O, tüm katılımcılar gibi, turun başlangıcından önce, her görevin ne zaman hazır olacağını, çözümü için ne kadar zaman ayrılacağını ve onu çözmek için kaç puan alabileceğinizi bilir. Artur yetenekli bir öğrencidir ve bu nedenle Olimpiyatta çözmeyi seçtiği herhangi bir sorunu ayrılan sürede başarılı bir şekilde çözebilecek ve doğrulama için geçebilecektir.
Arthur'un çözeceği optimal problem seçimi ile alabileceği maksimum puan sayısını ve bu problemlerin sayısını ve listesini belirleyen bir program yazılması gerekmektedir.
Girdi
İlk satır bir tamsayı n (1 ≤ n ≤ 10
5) içerir, Olimpiyattaki problem sayısı.
Sonraki n satır, problemlerin açıklamalarını içerir, her satırda üç sayı: si i-inci problemin dakika cinsinden ortaya çıktığı an, t
i dakika cinsinden çözümü için ayrılan süre ve ci kaç dakika katılımcının bu problemi çözdüğü için alacağı puan (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Künye
İlk satır tek bir sayı içermelidir – Arthur'un Olimpiyatlarda alabileceği maksimum puan.
İkinci satır bir tamsayı m içermelidir - optimum seçimle çözülecek görev sayısı.
Üçüncü satır, m boşlukla ayrılmış tamsayıları içermelidir - bu problemlerin çözüldükleri sırayla sayıları. Görevler, birden başlayarak giriş dosyasında tanımlandıkları sırayla numaralandırılır.
Birkaç uygun yanıt varsa, bunlardan herhangi birini yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |