Կարմիր և կապույտ ուղղանկյուններ
Փոքրիկ Նարեկը սիրում է ներկեր և ներկել։ Դրա համար հաճախ նրան անվանում են ներկարար Նարեկ։ Նարեկն ունի N հատ կարմիր ուղղանկյուն։ Ուղղանկյունների չափերը՝ լայնությունը և բարձրությունը բնական թվեր են։ Ուղղանկյունները դրված են իրար կողք կողքի x -երի առանցքի վրա։
Ներկարար Նարեկը ցանկանում է նկարել առավելագույնը K հատ կապույտ ուղղանկյուն այնպես, որ կարմիր ուղղանկյուններից յուրաքանչյուրը ծածկվի ճիշտ մեկ կապույտ ուղղանկյունով, սակայն մեկ կապույտ ուղղանկյունը կարող է ծածկել մեկից ավել կարմիր ուղղանկյուններ։ Նարեկն ազատ է կապույտ ուղղանկյունների չափերն ընտրելու հարցում, բայց նա ցանկանում է, որ նրանց մակերեսների գումարը, որքան հնարավոր է, քիչ լինի։
Գրեք ծրագիր, որը գտնում է կապույտ ուղղանկյունների մակերեսների մինիմալ հնարավոր գումարը։
Մուտքային տվյալներ
Առաջին տողում տրված են երկու ամբողջ N(2 ≤ N ≤ 200) և K (1 ≤ K ≤ 10 ) թվերը։
Հաջորդ N տողերից i -րդը պարունակում է երկու ամբողջ թվեր՝ հերթական կարմիր ուղղանկյան h_i բարձրություը և w_i լայնությունը (1 ≤ h_i , w_i ≤ 1000) ։
Ելքային տվյալներ
Պետք է արտածել մեկ ամբողջ թիվ՝ կարմիր ուղղանկյուններին ծածկող մինչև K հատ կապույտ ուղղանկյունների մակերեսների գումարի հնարավոր մինիմալ արժեքը։
Օրինակ
Մուտք | Ելք |
3 2
1 1
2 2
1 2 | 8 |
Ենթախնդիրներ
Ենթախնդիր 1 (15 միավոր) N,K ≤ 7
Ենթախնդիր 2 (19 միավոր) N ≤ 200, K = 1
Ենթախնդիր 3 (21 միավոր) N ≤ 200, K = 2
Ենթախնդիր 4 (15 միավոր) N ≤ 200, K = 998244353
Ենթախնդիր 5 (30 միավոր) N ≤ 200, K ≤ N - 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB