Sa valmistud osalema autorallis ja pead otsustama, millistes tanklates teel kütust võtta.</p>

Eeldused on:

• Tankimisele kulub $T$ minutit ($1 \le T \le 10^4$).
• Autosse mahub maksimaalselt $F_{\max}$ liitrit kütust ($10^3 \le F_{\max} \le 10^6$).
• Kütuse hulk $F$ väheneb iga läbitud kilomeetri lõpus hetkega $\Delta_F$ liitri võrra ($1 \le \Delta_F \le 50$).
• Auto kiirus ($S$ kilomeetrit minutis) kasvab kütuse väheneds, kuid päris ilma kütuseta auto ei sõida muidugi üldse; seos on \[\begin{equation*} S = \begin{cases} S_{max}-C \cdot F & \quad \textrm{kui} F > 0 \\ 0 & \quad \textrm{kui} F = 0 \end{cases} \end{equation*}\] ($10^3 \le S_{max} \le 10^6$, $1 \le C \le 10^2$ ja andmed on alati sellised, et $S \ge 0$).
• Ralli kogupikkus on $D$ kilomeetrit ($10^3 \le D \le 10^6$).
• Tanklate arv on $N$ ($1 \le N \le 25$).
• Tanklate asukohad on $M_i$, mis näitavad tankla kaugust stardist ($0 < M_i < D$ ja iga $i < j$ korral $M_i < M_j$).

Kirjutada programm, mis leiab optimaalsed tankimiskohad ja igas tanklas võetava kütuse hulga, et ralli minimaalse koguajaga läbi sõita.

입력 형식

Tekstifailis on järgmised täisarvud, igaüks eraldi real: $T$, $F_{\max}$, $\Delta_F$, $S_{\max}$, $C$, $D$, $N$, $M_1$, \ldots, $M_N$.

출력 형식

Tekstifaili esimesele reale väljastada täisarv $F_0$, stardis tangitava kütuse hulk. Faili teisele reale väljastada tankimispeatuste arv $K$. Järgmisele $K$ reale väljastada igaühele kaks täisarvu, tankla indeks ja selles tanklas võetava kütuse kogus. Peatused väljastada tanklate indeksite kasvamise järjekorras.

예제 입력

3
20000
2
150000
2
30000
2
10000
20000

예제 출력

20000
2
1 20000
2 20000