Василий өрөөгөө лаагаар гэрэлтүүлэх дуртай. Түүнд янз бүрийн төрлийн лаанууд байна.

Тэрээр нийт n төрлийн лаатай. Төрөл бүрийн лаа дараах шинж чанартай:

• a_i — тухайн төрлийн лааны тоо
• t_i — тухайн лаа хэдэн цаг асах

Василий лаануудыг нэг нэгээр нь асааж хэрэглэнэ.

Лаа бүр дуусахдаа 1 үлдэгдэл үлдээнэ. Василий эдгээр үлдэгдлийг ашиглан шинэ лаа хийж чадна. Тодруулбал:

• b ширхэг үлдэгдэл → 1 шинэ лаа

Шинээр хийсэн лаа нь 1 цаг асна.

Василий нийт хэдэн цаг өрөөгөө гэрэлтүүлж чадах вэ?

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоо өгөгдөнө: n b

Дараагийн n мөр бүрт хоёр бүхэл тоо байна: \(a_i t_i\)

• n — лааны төрөл
• b — хэдэн үлдэгдлээр 1 шинэ лаа хийх
• a_i — тухайн төрлийн лааны тоо
• t_i — тухайн лаа хэдэн цаг асах

Гаралт

Нэг бүхэл тоо хэвлэнэ:

• Василий өрөөгөө нийт хэдэн цаг гэрэлтүүлэх боломжтой

Хязгаарлалт

• 1 ≤ n ≤ 2 × 10^5
• 1 ≤ a_i ≤ 10^9
• 1 ≤ t_i ≤ 10^9
• 2 ≤ b ≤ 10^9

Дэд бодлого

Жишээ

Оролт-1

2 2
2 1
1 2

Гаралт-1

6

Тайлбар-1

Василийд:

• 2 ширхэг (1 цагийн) лаа → 2 цаг
• 1 ширхэг (2 цагийн) лаа → 2 цаг

Эхний нийт:

2 + 2 = 4 цаг

Нийт лаа = 2 + 1 = 3 → 3 үлдэгдэл

• 3 үлдэгдэл → 1 шинэ лаа → 1 цаг

Нийт:

4 + 1 = 5 цаг

Шинэ лаанаас 1 үлдэгдэл нэмэгдэж:

• нийт үлдэгдэл = 2 → дахин 1 лаа → 1 цаг

Эцэст нь:

5 + 1 = 6 цаг

Оролт-2

3 3
3 1
2 2
1 3

Гаралт-2

12