Dīvaino Skaitļu Karalistē notiek gada Lielā loterija. Katrs no karalistes iedzīvotājiem bez maksas saņem vienu tukšu loterijas biļeti. Lai piedalītos loterijā, biļetē jāieraksta viens vai vairāki naturāli skaitļi pēc kārtas. Lielākais skaitlis, ko drīkst ierakstīt biļetē, ir L.

Piemēram, ja L=20, tad biļetē var ierakstīt skaitli 17, skaitļus 3, 4, 5, skaitļus 10, 11, 12, 13, 14, 15, visus skaitļus no 1 līdz 20, bet nevar 10, 11, 12, 15, 16, 17 (skaitļi nav pēc kārtas) vai 19, 20, 21 (21 ir lielāks par 20). Lai piedalītos Lielajā Loterijā, biļetes īpašniekam par katru tajā ierakstīto skaitli jāsamaksā karalim D dālderus. 

Šogad karalis ir izdomājis, ka laimējušas būs tās biļetes, kurās būs ierakstīts vismaz viens pirmskaitlis (tāds naturāls skaitlis, kas lielāks par 1 un kam ir tikai divi dalītāji: 1 un pats skaitlis). Katras šādas biļetes īpašniekam karalis izmaksās laimestu, kas ir visu biļetē ierakstīto pirmskaitļu ciparu summa. Uzrakstiet programmu, kas palīdz karalim aprēķināt, cik daudz dālderu viņš nopelnīs, ja ir zināms, kādi skaitļi ir ierakstīti biļetēs!

Pirmajā rindā doti trīs naturāli skaitļi, kas atdalīti ar tukšumzīmēm: N (1≤N≤10⁵ ) – biļešu skaits, kas piedalās loterijā, D (1≤D≤100) – cena, cik maksā katrs biļetē ierakstītais skaitlis un L – lielākais skaitlis, ko drīkst ierakstīt biļetē (2≤L≤2·10⁶ ). Nākošajās N rindās katrā doti divi skaitļi ai un bi, kas atdalīti ar tukšumzīmi un norāda, ka i–tais iedzīvotājs ierakstījis biļetē visus skaitļus no a_i līdz b_i ieskaitot (1≤a_i≤b_i≤L).

Jāizvada viens vesels skaitlis – dālderu daudzums, kādu karalis nopelnīs. Ja karalis laimestos izmaksā vairāk dālderu nekā saņēmis par ierakstītajiem skaitļiem, tad skaitlis jāizvada ar mīnuszīmi. 

Apakšuzdevumi

• N = 1 (10 punkti)
• L < 104 (10 punkti)
• N < 1000 (20 punkti) 

1. testa piemēra paskaidrojums

Pirmais iedzīvotājs, kas piedalās loterijā, ir ierakstījis skaitļus 2, 3, 4, 5, iztērējis 12, bet laimējis 2+3+5=10 dālderus, otrais - ierakstījis 1, 2, 3, 4, 5, 6, iztērējis 18, bet laimējis 2+3+5=10 dālderus, trešais - ierakstījis 16, 17, 18, 19, iztērējis 12, bet laimējis 1+7+1+9=18 dālderus. Karalis ir ieņēmis 12+18+12=42 dālderus, bet izmaksājis laimestos 10+10+18 = 38 dālderus. Karalis ir nopelnījis četrus dālderus. 

2. testa piemēra paskaidrojums

Abi iedzīvotāji, kas piedalās loterijā, ir ierakstījuši skaitļus 71, 72, 73, katrs iztērējis 15, bet laimējis 7+1+7+3=18 dālderus. Karalis ir ieņēmis 15+15=30 dālderus, bet izmaksājis laimestos 18+18 = 36 dālderus. Karalis ir zaudējis sešus dālderus.