Դավիթն ունի N մետաղադրամների հավաքածու, որոնցից յուրաքանչյուրն ունի որոշակի անվանական արժեք։ Վերջերս սակայն, նա գտել է չափազանց հազվագյուտ մետաղադրամ մեկ այլ դրամագետի հավաքածուում, և որոշել է այն ձեռք բերել։ Հազվագյուտ մետաղադրամի տերը համաձայն է փոխանակել։ Նա կտրամադրի մետաղադրամը Դավիթին, եթե նա տա նրան մի քանի մետաղադրամներ, որոնց ընդհանուր անվանական արժեքը առնվազն P է: Այժմ Դավիթը մտածում է, թե որ մետաղադրամները տա, որ մնացածում տարբեր արժեքներով մետաղադրամների քանակը լինի մաքսիմալ։
Բացի այս առաջնահերթ նպատակից, որ Դավիթը ցանկանում է ամեն գնով իրականացնել, նա ուզում է, որպեսզի այն մետաղադրամների արժեքների գումարը, որոնք կփոխանակվեն ցանկալի մետաղադրամի հետ, հնարավորինս փոքր լինի: Գրեք ծրագիր, որն օգնում է նրան կատարել այս դժվար ընտրությունը:
Մուտքային տվյալներ
Առաջին տողում տրված են երկու ամբողջ թիվ N և P թվերը: Երկրորդ տողը պարունակում է N ոչ բացասական ամբողջ թվերը, որոնք սահմանում են մետաղադրամների արժեքները:
Ելքային տվյալներ
Ելքի առաջին տողում արտածեք երկու ամբողջ թվեր D և S (S ≥ P)՝ տարբեր անվանական արժեքների թիվը, որոնք մնում են Դավիթի մոտ, և փոխանակման ժամանակ օգտագործված մետաղադրամների արժեքների գումարը:
Օրինակ
Մուտք
Ելք
8 21
1 5 5 5 0 7 4 7 9
4 21
7 100
90 2 2 3 3 6 6
3 101
Բացատրություն
Առաջին օրինակում մնում են {0, 4, 5, 5, 7} մետաղադրամները, որոնցում կան 4 տարբեր արժողությամբ մետաղադրամներ։ Կա այլընտրանքային լուծում՝ {4, 5, 5, 7}:
Երկրորդ օրինակում մնում են {2, 3, 6} երեք մետաղադրամները։ Իսկ տրվող մինիմալ գումարը 101 է։