{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePak Dengklek ingin mengundang tamu untuk mengikuti pesta dansa. Setiap tamu memiliki berat senilai \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e dan nilai kecantikan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Setiap tamu juga memiliki sejumlah teman. Setiap teman terbagi menjadi beberapa kelompok. Dua orang tamu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e dan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e berada dalam kelompok yang sama jika dan hanya jika terdapat untaian tamu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e dimana \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e dan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e adalah teman untuk setiap \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e dan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\n\n\u003cp\u003ePak Dengklek akan menyiapkan panggung untuk pesta dansa tersebut. Panggung yang ada dapat menampung maksimal total berat tamu senilai \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eW\u003c/i\u003e\u003c/span\u003e. \u003c/p\u003e\n\u003cp\u003ePak Dengklek ingin mengundang tamu-tamu sedemikian sehingga total berat dari semua tamu yang diundang tidak melebihi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eW\u003c/i\u003e\u003c/span\u003e dan total kecantikan dari setiap tamu yang diundang semaksimal mungkin. \n\n\u003cp\u003eSelain itu, untuk setiap kelompok pertemanan, ia dapat melakukan salah satu hal berikut : mengundang semua tamu pada kelompok tersebut, ATAU tidak lebih dari 1 tamu dari kelompok tersebut. Bantu Pak Dengklek mencari nilai total kecantikan maksimal yang dapat diperoleh dan total berat dari tamu-tamu yang diundang tidak melebihi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eW\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eBaris pertama berisi tiga buah bilangan bulat \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e dan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eW\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1000\u003c/span\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/863123c37f0f9787f5ab0a5232e0e190?v\u003d1656377558\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eW\u003c/i\u003e ≤ 1000\u003c/span\u003e)\u0026nbsp;— banyaknya tamu, banyaknya pasangan tamu yang berteman satu saa lain dan total berat maksimal dari panggung yang digunakan untuk menampung tamu.\u003c/p\u003e\n\u003cp\u003eBaris kedua berisi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e buah bilangan bulat \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 1000\u003c/span\u003e)\u0026nbsp;— berat dari setiap tamu.\u003c/p\u003e\n\u003cp\u003eBaris ketiga berisi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— kecantikan dari masing-masing tamu.\u003c/p\u003e\n\n\u003cp\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e baris berikutnya berisi hubungan pertemanan, baris ke the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e berisi dua buah bilangan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e dan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e), yang berarti \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e dan \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e berteman. Pertemanan bersifat dua arah. Setiap pasangan \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e berbeda.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eNilai kecantikan total maksimal dari tamu-tamu yang diundang Pak Dengklek dimana total beratnya tidak melebihi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eW\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 1 5\n3 2 5\n2 4 2\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2 11\n2 4 6 6\n6 4 2 1\n1 2\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eDi contoh pertama terdapat dua kelompok tamu: Tamu \u003cspan class\u003d\"tex-span\"\u003e{1, 2}\u003c/span\u003e dan tamu \u003cspan class\u003d\"tex-span\"\u003e{3}\u003c/span\u003e. Cara terbaik adalah memilih semua tamu pada kelompok pertama, total berat mereka adalah \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e dan total nilai kecantikan mereka adalah \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eDi kelompok kedua terdapat dua kelompok teman: Tamu \u003cspan class\u003d\"tex-span\"\u003e{1, 2, 3}\u003c/span\u003e dan tamu \u003cspan class\u003d\"tex-span\"\u003e{4}\u003c/span\u003e. Pak Dengklek tidak bisa mengundang semua tamu dari kelompok pertama karena total berat mereka adalah \u003cspan class\u003d\"tex-span\"\u003e12 \u0026gt; 11\u003c/span\u003e, maka cara optimal adalah mengundang tamu pertama dari kelompok pertama dan satu-satunya tamu pada kelompok kedua. Total berat mereka adalah \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e, dan total kecantikan mereka adalah \u003cspan class\u003d\"tex-span\"\u003e7\u003c/span\u003e.\u003c/p\u003e"}}]}