Pareidolia (Gold)

Cho xâu $s$ gồm các chữ cái Latin thường, ký tự thứ $i$ có chi phí xóa $w_i$.

Bạn được chọn một tập ký tự bất kỳ (có thể rỗng) để xóa khỏi $s$. Các ký tự còn lại giữ nguyên thứ tự cũ và ghép sát lại thành xâu $t$. Chi phí của cách xóa bằng tổng $w_i$ của các ký tự bị xóa.

Gọi $B(t)$ là số lần xâu "bessie" xuất hiện trong $t$ dưới dạng xâu con liên tiếp. Hai lần xuất hiện của "bessie" không bao giờ chồng lấn nhau, nên $B(t)$ chính là số đoạn con liên tiếp bằng "bessie" trong $t$.

Hãy tìm giá trị lớn nhất của $B(t)$ trên mọi cách xóa, và trong những cách xóa đạt được giá trị lớn nhất đó, tìm chi phí nhỏ nhất.

Dữ liệu vào

• Dòng 1: xâu $s$ chỉ gồm chữ cái Latin thường.
• Dòng 2: $|s|$ số nguyên $w_1,w_2,\dots ,w_{|s|}$, chi phí xóa từng ký tự.

Dữ liệu ra

Hai dòng:

• Dòng 1: giá trị lớn nhất của $B(t)$.
• Dòng 2: chi phí xóa nhỏ nhất để đạt được giá trị đó.

Ràng buộc

• $1\le |s|\le 2\times {10}^5$
• $1\le w_i\le 1000$
• Có những test với $|s|\le 2000$, và những test mà mọi $w_i$ đều bằng $1$.

Ví dụ